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)

Answer 3

This solution is going to involve a bit of itertools.permutations usage, set(), and some good ol' fashioned set difference. Bear in mind, the runtime for finding a permutation will still be O(n!). My solution won't do it in-line, either, but there may be a much more elegant solution that allows you to do so (and doesn't involve itertools.permutations). For this purpose, this is the straightforward way to accomplish the task.

Step 1: Algorithm for generating cycles, using the first element given. For a list [1, 1, 2, 2], this will give us [1, 1, 2, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 2, 1, 1].

def rotations(li):
    count = 0
    while count < len(li):
        yield tuple(li)
        li = li[1:] + [li[0]]
        count += 1

Step 2: Importing itertools.permutations to give us the permutations in the first place, then setting up its results into a set.

from itertools import permutations
perm = set(permutations([1, 1, 2, 2]))

Step 3: Using the generator to give us our own set, with the cycles (something we want to rid ourselves of).

cycles = set(((i for i in rotations([1, 1, 2, 2]))))

Step 4: Apply set difference to each and the cycles are removed.

perm = perm.difference(cycles)

Hopefully this will help you out. I'm open to suggestions and/or corrections.

Answer 4

First I'll show the containers and algorithms we'll be using:

#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <iterator>

using std::vector;
using std::set;
using std::sort;
using std::next_permutation;
using std::copy;
using std::ostream_iterator;
using std::cout;

Next our vector which will represent the Permutation:

typedef vector<unsigned int> Permutation;

We need a comparison object to check whether a permutation is a rotation:

struct CompareCyclicPermutationsEqual
{
    bool operator()(const Permutation& lhs, const Permutation& rhs);
};

And typedef a set which uses the cyclic comparison object:

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations;

Then the main function is quite simple:

int main()
{
    Permutation permutation = {1, 2, 1, 2};
    sort(permutation.begin(). permutation.end());

    Permutations permutations;

    do {
        permutations.insert(permutation);
    } while(next_permutation(numbers.begin(), numbers.end()))


    copy(permutations.begin(), permutations.end(),
         ostream_iterator<Permutation>(cout, "\n");

    return 0;
}

Output:

1, 1, 2, 2,
1, 2, 1, 2,

I haven't implemented CompareCyclicPermutationsEqual yet. Also you'd need to implement ostream& operator<<(ostream& os, const Permutation& permutation).