Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Permutations in reverse order

by wanna_code_perl (Friar)
on Mar 01, 2013 at 22:39 UTC ( [id://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 (Patriarch) 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 (Patriarch) 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?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (7)
As of 2024-03-19 02:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found