XP is just a number PerlMonks

### Permutations

by octothorpe (Initiate)
 on Mar 22, 2001 at 03:31 UTC Need Help??
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)));

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")
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.
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).

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")

Create A New User
Node Status?
node history
Node Type: perlquestion [id://66186]
Approved by root
help
Chatterbox?
and a soft breeze sighs...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2018-04-23 04:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (84 votes). Check out past polls.

Notices?