Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Permutations in reverse order

by wanna_code_perl (Pilgrim)
on Mar 01, 2013 at 22:39 UTC ( #1021356=perlquestion: print w/replies, xml ) Need Help??
wanna_code_perl has asked for the wisdom of the Perl Monks concerning the following question:

I've been scouring CPAN directly and via Google for a module that will iterate permutations in reverse order, but have come up empty. I would rather not roll my own.

I ask because I'm working on a search algorithm where I need to find the maximum permutation that meets the search criteria, but with ~8.7e10 permutations, searching them all is a huge waste.

I want to be able to do something like the below code. Of course Algorithm::Permute has no prev() method (nor does it actually guarantee any order), and neither do any of the other permutation/combinatorics modules I could find.

Alternatively, is there a clever way to (ab)use ascending permutations to get descending ones that I can't see right now?

use Algorithm::Permute; say join ",",search(reverse (1..14)); sub search { my $p = new Algorithm::Permute(\@_); while (my @a = $p->prev) { return @a if copasetic(@a); } }

Replies are listed 'Best First'.
Re: Permutations in reverse order (easy)
by tye (Sage) on Mar 02, 2013 at 02:04 UTC

    Simply replace each element of a returned permutation with 15-$_.

    - tye        

      Thank you, tye. You know, I had tried this early on, but discarded the idea at the time because I was still getting inconsistent results with Algorithm::Permute. Algorithm::Permute explicitly doesn't guarantee any order to its results, but it was ordered when the items where initially in lex order (which mine were not). I later found the fine print in the docs, but I didn't think to revisit the $max - $_ transformation. Switching to Algorithm::Loops, combined with this $max - $_ suggestion, was the solution.

Re: Permutations in reverse order
by Khen1950fx (Canon) on Mar 02, 2013 at 00:52 UTC
    Something like this? Warning: the resulting list of descending permutations will list every descending permutation, and it only stops when it returns to the original ascending list.
    #!/usr/bin/perl -l use strict; use warnings; use Algorithm::Loops qw(NextPermute); my(@list) = (1..14); do { print join(",", reverse @list); } while( NextPermute(@list) );
Re: Permutations in reverse order
by BrowserUk (Pope) on Mar 02, 2013 at 00:17 UTC

    What are you permuting? And what ordering are you seeking?

Re: Permutations in reverse order
by BrowserUk (Pope) on Mar 02, 2013 at 13:03 UTC

    Is this the ordering you want?

    perl -MAlgorithm::Combinatorics=permutations -E"@a=reverse 1..14; $i=permutations([0..13]); say join' ', @a[@$_] wh +ile $_=$i->next" 14 13 12 11 10 9 8 7 6 5 4 3 2 1 14 13 12 11 10 9 8 7 6 5 4 3 1 2 14 13 12 11 10 9 8 7 6 5 4 2 3 1 14 13 12 11 10 9 8 7 6 5 4 2 1 3 14 13 12 11 10 9 8 7 6 5 4 1 3 2 14 13 12 11 10 9 8 7 6 5 4 1 2 3 ...

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1021356]
Approved by Old_Gray_Bear
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2017-04-23 23:10 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (433 votes). Check out past polls.