FAQ 4.51 How do I permute N elements of a list?

Discussion in 'Perl Misc' started by PerlFAQ Server, Mar 6, 2011.

  1. This is an excerpt from the latest version perlfaq4.pod, which
    comes with the standard Perl distribution. These postings aim to
    reduce the number of repeated questions as well as allow the community
    to review and update the answers. The latest version of the complete
    perlfaq is at http://faq.perl.org .

    --------------------------------------------------------------------

    4.51: How do I permute N elements of a list?

    Use the "List::permutor" module on CPAN. If the list is actually an
    array, try the "Algorithm::permute" module (also on CPAN). It's written
    in XS code and is very efficient:

    use Algorithm::permute;

    my @array = 'a'..'d';
    my $p_iterator = Algorithm::permute->new ( \@array );

    while (my @perm = $p_iterator->next) {
    print "next permutation: (@perm)\n";
    }

    For even faster execution, you could do:

    use Algorithm::permute;

    my @array = 'a'..'d';

    Algorithm::permute::permute {
    print "next permutation: (@array)\n";
    } @array;

    Here's a little program that generates all permutations of all the words
    on each line of input. The algorithm embodied in the "permute()"
    function is discussed in Volume 4 (still unpublished) of Knuth's *The
    Art of Computer Programming* and will work on any list:

    #!/usr/bin/perl -n
    # Fischer-Krause ordered permutation generator

    sub permute (&@) {
    my $code = shift;
    my @idx = 0..$#_;
    while ( $code->(@_[@idx]) ) {
    my $p = $#idx;
    --$p while $idx[$p-1] > $idx[$p];
    my $q = $p or return;
    push @idx, reverse splice @idx, $p;
    ++$q while $idx[$p-1] > $idx[$q];
    @idx[$p-1,$q]=@idx[$q,$p-1];
    }
    }

    permute { print "@_\n" } split;

    The "Algorithm::Loops" module also provides the "NextPermute" and
    "NextPermuteNum" functions which efficiently find all unique
    permutations of an array, even if it contains duplicate values,
    modifying it in-place: if its elements are in reverse-sorted order then
    the array is reversed, making it sorted, and it returns false; otherwise
    the next permutation is returned.

    "NextPermute" uses string order and "NextPermuteNum" numeric order, so
    you can enumerate all the permutations of 0..9 like this:

    use Algorithm::Loops qw(NextPermuteNum);

    my @list= 0..9;
    do { print "@list\n" } while NextPermuteNum @list;



    --------------------------------------------------------------------

    The perlfaq-workers, a group of volunteers, maintain the perlfaq. They
    are not necessarily experts in every domain where Perl might show up,
    so please include as much information as possible and relevant in any
    corrections. The perlfaq-workers also don't have access to every
    operating system or platform, so please include relevant details for
    corrections to examples that do not work on particular platforms.
    Working code is greatly appreciated.

    If you'd like to help maintain the perlfaq, see the details in
    perlfaq.pod.
     
    PerlFAQ Server, Mar 6, 2011
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Yuan Zhong

    function to permute a string

    Yuan Zhong, Aug 4, 2004, in forum: C Programming
    Replies:
    2
    Views:
    454
    CBFalconer
    Aug 5, 2004
  2. Michael McGarry

    Randomly permute a list of integers

    Michael McGarry, Aug 8, 2006, in forum: C Programming
    Replies:
    6
    Views:
    593
  3. Phlip
    Replies:
    17
    Views:
    247
    Rick DeNatale
    May 18, 2009
  4. kj
    Replies:
    1
    Views:
    146
  5. PerlFAQ Server

    FAQ 4.51 How do I permute N elements of a list?

    PerlFAQ Server, Feb 7, 2011, in forum: Perl Misc
    Replies:
    0
    Views:
    160
    PerlFAQ Server
    Feb 7, 2011
Loading...

Share This Page