Do you want to match on parts of the string, eg just "Joe Fred," as well as combinations involving *all* the words? If so, here's a version which implements japhy's wicked combination routine from a query of mine here:

my $file = "xxxxxxxxx Joe xxxxxxx Fred xxxxxxxx Joe Fred Software xxxx
+xxx Inc Software Fred Joe";

my $string = "Joe Fred Software Inc";
my @n = split / /, $string;
my $max = 2**@n;
for (my $i = 0; $i < $max; ++$i)
{    my ($bits, @used) = $i;
    while ($bits)
    {    my $high_bit = int(log($bits)/log(2));
        push @used, $n[$high_bit];
        $bits &= ~(2**$high_bit);
    }
    my $match =  join " ", @used;
    print "$match\n" if $file =~ m/$match/;
}
[download]

Hope that's the kind of thing you wanted.