Permutations in reverse order

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);
    }
}
[download]

Comment on Permutations in reverse order Select or Download Code

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	[reply]
Re^2: Permutations in reverse order (easy) by wanna_code_perl (Friar) on Mar 02, 2013 at 09:19 UTC
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.	[reply] [d/l] [select]
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) );` [download]	[reply] [d/l]
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?	[reply]
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 ...` [download] 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.	[reply] [d/l]