Permutations

octothorpe has asked for the wisdom of the Perl Monks concerning the following question:

Below is a sub I've written to figure out all the possible arrangements of the elements of an array. Is there a cleaner and/or more efficient way to do this? I'm assuming that it would be possible to do this by swapping elements, thereby not copying the array each time, but I can't determine the order you'd need to swap them in.

sub combinations {
  my @array = @_;
  if ($#array == 0) {return [ $array[0] ]; }
  my @results;
  my $element;
  foreach $element (0..$#array) {
    my @leftovers = @array;
    my $chosen_one = splice(@leftovers, $element, 1);
    foreach (&combinations(@leftovers)) {
      push(@results, [ $chosen_one, @{$_} ]);
    }
  }
  return @results;
}

use Data::Dumper;
print Dumper(&combinations(qw(a b c d)));
[download]

Comment on Permutations Download Code

Replies are listed 'Best First'.
(tye)Re: Permutations by tye (Sage) on Mar 22, 2001 at 03:54 UTC
"Combinations" is picking subsets where order doesn't matter. For "permutations", order matters and you use the full set, not subsets. So mentioning "combinations" when computing permutations is going to confuse people. My favorite is Permuting with duplicates and no memory. A simple search or Super Search will turn up lots of other ones. - tye (but my friends call me "Tye")	[reply]
Re: Permutations by indapa (Monk) on Mar 22, 2001 at 06:21 UTC
You might also want to consult the Perl Cookbook recipe 4.19, it discusses solutions to generate all possible permutations of an array.	[reply]
Re: Permutations by dvergin (Monsignor) on Mar 22, 2001 at 03:37 UTC
meryln has written a ~~column~~ post on this (and probably a column, too).	[reply]
(tye)Re2: Permutations by tye (Sage) on Mar 22, 2001 at 09:04 UTC
Actually that post contains code that claims to do "permutations" but that does something different than what the original poster is doing (and different than what I think of when "permutations" are requested) [ the "combinations" part of the code does that I would call "combinations" :) ]. merlyn's code gives all of the different ways of picking one item each from a collection of sets. Both my and the above permutations code gives all of the possible orderings of the items in a single set (though my code gives only unique orderings in cases when there are duplicates in the "set"). I mention this not to claim that my definition of "permutations" is the one true and correct definition, but to point out the difference to help prevent further confusion. (: - tye (but my friends call me "Tye")	[reply]