Generating all permutations excluding cyclic rotations

Question

So I need an algorithm to generate all permutations of a list of numbers excluding cyclic rotations (e.g. [1,2,3] == [2,3,1] == [3,1,2]).

When there is at least 1 unique number in the sequence it is fairly straight forward, take out that unique number, generate all permutations of the remaining numbers (but with a small modification to the 'standard' permutations algorithm) and add the unique number to the front.

For generating the permutations I've found that it's necessary to change the permutations code to:

def permutations(done, options)
    permuts = []
    seen = []
    for each o in options
        if o not in seen
            seen.add(o)
            permuts += permutations(done+o, options.remove(o))
    return permuts

Only using each unique number in options once means that you don't get 322 twice.

This algorithm still outputs rotations when there are no unique elements, e.g. for [1,1,2,2] it would output [1,1,2,2], [1,2,2,1] and [1,2,1,2] and the first two are cyclic rotations.

So is there an efficient algorithm that would allow me to generate all the permutations without having to go through afterwards to remove cyclic rotations?

If not, what would be the most efficient way to remove cyclic rotations?

NOTE: this is not using Python, but rather C++.

Answer 1

For the case of permutations where all numbers are distinct, this is simple. Say the numbers are 1,2,...,n, then generate all permutations of 1,2,...,n-1 and stick n at the front. This gives all permutations of the full set modulo cyclic rotations. For example, with n=4, you would do

4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

This ensures that some cyclic rotation of each permutation of 1,2,3,4 appears exactly once in the list.

For the general case where you want permutations of a multiset (repeated entries allowed), you can use a similar trick. Remove all instances of the largest letter n (similar to ignoring the 4 in the above example) and generate all permutations of the remaining multiset. The next step is to put the ns back into the permutations in canonical ways (similar to putting the 4 at the beginning in the above example).

This is really just a case of finding all Lyndon words to generate necklaces

Answer 2

Think about testing each of the permutations you output, looking for a cyclic rotation that's "lexically" earlier than the one you've got. If there is one, don't return it - it will have been enumerated somewhere else.

Choosing a "unique" first element, if one exists, helps you optimize. You know if you fix the first element, and it's unique, then you can't possibly have duplicated it with a rotation. On the other hand, if there's no such unique element, just choose the one that occurs the least. That way you only need to check for cyclic rotations that have that first element. (Example, when you generate [1,2,2,1] - you only need to check [1,1,2,2], not [2,2,1,1] or [2,1,1,2]).

---

OK, pseudocode... clearly O(n!), and I'm convinced there's no smarter way, since the case "all symbols different" obviously has to return (n-1)! elements.

// generate all permutations with count[0] 0's, count[1] 1's...
def permutations(count[])
    if(count[] all zero)
        return just the empty permutation;
    else
        perms = [];
        for all i with count[i] not zero
            r = permutations(copy of count[] with element i decreased);
            perms += i prefixed on every element of r
        return perms;

// generate all noncyclic permutations with count[0] 0's, count[1] 1's...
def noncyclic(count[])
    choose f to be the index with smallest count[f];
    perms = permutations(copy of count[] with element f decreased);
    if (count[f] is 1)
        return perms;
    else
        noncyclic = [];
        for each perm in perms
            val = perm as a value in base(count.length);
            for each occurence of f in perm
                test = perm rotated so that f is first
                tval = test as a value in base(count.length);
                if (tval < val) continue to next perm;
            if not skipped add perm to noncyclic;
        return noncyclic;

// return all noncyclic perms of the given symbols
def main(symbols[])
    dictionary = array of all distinct items in symbols;
    count = array of counts, count[i] = count of dictionary[i] in symbols
    nc = noncyclic(count);
    return (elements of nc translated back to symbols with the dictionary)