This is not quite what BrowserUk's regex (or /fred/ && /bill/ for that matter) matches.

The main advantage of the lookaheads over multiple regex is that it extends linearly rather than compounding.

#! perl -slw
use strict;
use List::Util qw[ shuffle ];

my @terms = qw[
    the quick brown fox jumps over the lazy dog
];

my $re = join'', map "(?=^.*$_)", @terms;
$re = qr/$re/;

for( 1 .. 10) {
    my $input = join ' ', shuffle @terms;
    $input =~ $re and print "$input matched";
}

__END__
C:\test>junk48
quick brown the dog over fox lazy jumps the matched
the dog over jumps the quick lazy brown fox matched
jumps brown fox lazy quick the over dog the matched
jumps brown dog over the fox lazy the quick matched
over dog jumps fox the brown the lazy quick matched
dog fox lazy the the quick over brown jumps matched
lazy over brown dog quick the fox jumps the matched
jumps fox quick brown the over lazy dog the matched
over dog the lazy jumps quick brown fox the matched
dog over lazy quick the the jumps brown fox matched
[download]

That is considerably easier than constructing and trying all 350,000+ regex.

Another advantage is that it only takes a small tweak to deal with the situation where not just the ordering is uncertain, but also some terms may be omitted. With the nice side-effect that you can use capturing to find out what was matched because the captures will be returned in a consistent ordering:

#! perl -slw
use strict;
use List::Util qw[ shuffle ];

my @terms = qw[
    the quick brown fox jumps over the lazy dog
];

my $re = join'', map "(?=^.*($_))?", @terms;
$re = qr/$re/;

for( 1 .. 10) {
    my $input = join ' ', (shuffle @terms)[ 1 .. 5 ];
    my @found = $input =~ $re;
    $_ //= 'n/a' for @found;
    print "Found [ @found ]\nin:'$input'";
}

__END__
C:\test>junk48
Found [ the n/a n/a fox n/a over the lazy dog ]
in:'fox over lazy the dog'
Found [ n/a n/a brown fox n/a over n/a lazy dog ]
in:'fox lazy dog brown over'
Found [ the quick brown fox n/a n/a the n/a dog ]
in:'the quick dog fox brown'
Found [ n/a n/a brown fox jumps over n/a lazy n/a ]
in:'brown lazy over jumps fox'
Found [ the quick brown n/a jumps n/a the lazy n/a ]
in:'lazy the quick brown jumps'
Found [ the quick n/a n/a jumps n/a the n/a dog ]
in:'dog quick the the jumps'
Found [ n/a quick brown fox jumps n/a n/a n/a dog ]
in:'fox jumps quick brown dog'
Found [ the n/a brown n/a n/a over the lazy dog ]
in:'over lazy the dog brown'
Found [ the n/a brown fox jumps n/a the n/a dog ]
in:'the brown dog fox jumps'
Found [ the quick n/a fox n/a over the lazy n/a ]
in:'fox lazy over quick the'
[download]

The double matching of 'the' can be a good or bad thing depending upon your purpose.