permutations?

[eduardo]

let us say we have a hash of lists that looks like this:

my $words = {
   'lng'       => ['lang', 'long', 'leng', 'loo'],
   'sentance'  => ['sentence'],
   'thxs'      => ['this', 'thus']
};

and we want to run it through some transform that will give us an array of every single possible combination of words from each family of keys, in this case:

lang sentence this
long sentence this
leng sentence this
loo sentence this
lang sentence thus
long sentence thus
leng sentence thus
loo sentence thus

not neccesseraly in that order, order is unimportant, as long as I had all the possible combinations... what is a good perlish way to do this?

[merlyn]

Untested, but I often get this stuff right on the first try... :)

my $words = { 
   'lng'       => ['lang', 'long', 'leng', 'loo'], 
   'sentance'  => ['sentence'], 
   'thxs'      => ['this', 'thus'] 
};
print map "$_\n", phol($words);
sub phol {
  my($key, $value, @rest) = %{+shift};
  if (@rest) {
    return map { my $r = $_; map { "$_ $r" } @$value } phol({@rest});
  } else {
    return @$value;
  }
}

-- Randal L. Schwartz, Perl hacker

[Anonymous Monk]

Is there any easier way to get values listed as permutations? I mean I can't use those Perl things at all. And I would like to get all 120 permutations of five letters listed. Is there any way find such program without programming? [e-mail]

[sean]

Hmmm...

my %words = (
   'lng'        => ['lang','long','leng','loo'],
   'sentance'   => ['sentence'],
   'thxs'       => ['this','thus']
);

my @results;

for my $key (keys %words) {
  if (defined(@results)) {
    @results = &loljoin(\@results, $words{$key}); 
  } else {
    @results = map {[$_]} @{$words{$key}};
  }
}


sub loljoin {                 #pass me two references to arrays:
  my @results = @{(shift)};   #the results so far..
  my @newwords = @{(shift)};  #and the set to add to our results
  my @newresults;
  for my $word (@newwords) {
    for my $result (@results) {
      push(@newresults,[@$result, $word]);
    }
  }
  return @newresults;
}

# results are in @results as a list of lists
# eg: for my $foo { print join(" ",@$foo) . "\n" }

Hmm, well. That appears to work, but it doesn't look as good as it could.

[btrott]

Sounds like you want a slight adaptation of this FAQ: How do I permute N elements of a list?.

[plaid]

You say that order is unimportant, but do you mean that the sentences can be in any order at all? You're using a hash reference to store the keys 'lng', 'sentance', and 'thxs', but hashes don't preserve any order whatsoever, so you're likely not going to get the keys in the same order you entered them into $words. If you want to keep the sentence parts in the same order, you might want to instead make it an array reference

my $words = [
   ['lang', 'long', 'leng', 'loo'],
   ['sentence'],
   ['this', 'thus']
];

[eduardo]

the order of the words isn't important at all, as long as one word from every key becomes part of each candidate answer... and unfortunately they are being passed to me as a hash of lists, so, i have to deal with them that way. (from another object) however, in the answer i can definetly mangle it any way we see fit...

[fglock]

You could install module Algorithm::Permute, then try this:

use Algorithm::Permute;

my $p = new Algorithm::Permute(['a'..'e']);
while (@res = $p->next) {
    print join(", ", @res), "\n";
}

[shotgunefx]

You could use this snippet like so.

my $iter = make_permutator( values%{$words} );
while (my @els = $iter->() ){
    print join (" ",@els)"\n";
}



-Lee

"To be civilized is to deny one's nature."