For testing purposes it is often useful to generate permutations on a list through an iterator (like tye's Derangements iterator).
Sometimes we need random permutations, but for some applications it is
necessary that there is an order in the generated permutations.
I am using the following order on permutations. If the list to be
permuted consists of increasing digits, then the permutations are
numbered such that the concatenated digits of each permutation would
give monotonically increasing values.
Like that:
$ perl -w permute_n.pl 3
0: 1,2,3
1: 1,3,2
2: 2,1,3
3: 2,3,1
4: 3,1,2
5: 3,2,1
More control compared to an iterator is given by the 'random-access'
permutation 'accessor' that can generate the n-th ordered permutation
directly (thus 'random access').
For example you might want to use every n-th permutation or simply step
backwards through the permutations. Maybe you are interested only in
permutations on prime number positions...
For such purposes the following program allows flexible access. If the
list of elements is large, it can avoid a lot wasteful calculating.
For example generate the first, third, fifth, and then the fifth last,
third last, and the last permutation of the list of numbers 1..18:
$ perl -w permute_n.pl 18 0 2 4 -5 -3 -1
0: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
2: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,16,18
4: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,16,17
6402373705727995: 18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,1,3,2
6402373705727997: 18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,2,3,1
6402373705727999: 18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
On the other hand, if all permutations are needed, any iterator would probably outperform this generator.
Enjoy.
|
[Offer your reply]
|