Subscribe to DSC Newsletter

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.

Tags: keyword clustering, n-gram, permutations, text mining

Views: 332

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.

RSS

On Data Science Central

© 2019   AnalyticBridge.com is a subsidiary and dedicated channel of Data Science Central LLC   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service