Perl Monk, Perl Meditation PerlMonks

### Permutations in reverse order

by wanna_code_perl (Pilgrim)
 on Mar 01, 2013 at 22:39 UTC 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.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1021356]
Approved by Old_Gray_Bear
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2018-05-22 18:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (165 votes). Check out past polls.

Notices?