# AnalyticBridge

Subscribe to Vincent Granville's Weekly Digest:

# n-grams: permutation generators

I am looking for an algorithm that generates all permutations of order n. I wrote a paper on random permutations in the past, based on the Chinese remainder theorem, and I believe that it provides simple tools to solve this problem. Also, I've found interesting Perl code for permutation generation:

use List::Permutor;

my \$permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = \$permutor->next() ) {
print "@permutation\n";
}

and also

my @arr = (0, 1, 2);
my \$iter = getPermIter(@arr);
while (my @perm = \$iter->next() ){
print "@perm\n";
}

(see http://stackoverflow.com/questions/635768/how-can-i-generate-all-pe... for details about these scripts).

I am wondering if there is a root permutation s, for any order n, such that powers of this root permutation (s, s^2, s^3, ... , s^{n!}) covers all the n! permutations of order n. I guess this is a group theory problem, and s must not have cycles of length < n (in other words, s must be a permutation of maximum cycle). Once such a permutation is found, it is straightforward to generate all permutations of order n.

For n=2, s=(2,1) is the only root permutation
For n=3, s=(2,3,1) is a root permutation
For n=4, s=?

If such a root permutation does not exist (for a particular n), I am wondering if we could find 2 base permutations say s and t, such that their products s^k * t^m (over all integers k, m) cover all permutations of order n.

Views: 82

### Replies to This Discussion

in the R package "gtools" there are some nice functions that return permutations and combinations. The functions are called permutations and combinations.

To see the mechanics, you can just type the commands inside the R environment (once you have the gtools package installed). They both use a function called Recall, which I think allows iterative function calls. I happened to be reading about Recall earlier today.

Hope this helps.

1

2

3

4

5

6

7

8

9

10