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.