Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Permutations

by octothorpe (Initiate)
on Mar 22, 2001 at 03:31 UTC ( #66186=perlquestion: print w/ replies, xml ) 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)));

Comment on Permutations
Download Code
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")
(tye)Re: Permutations
by tye (Cardinal) 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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://66186]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2014-09-16 22:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (51 votes), past polls