Geek Answers Handbook

Generation of all permutations excluding cyclic rotations

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

If the sequence has at least 1 unique number, it is fairly straightforward, remove this unique number, generate all the permutations of the remaining numbers (but with a slight modification of the "standard" permutation algorithm) and add a unique number in front.

To create permutations, I found that it was necessary to change the permutation 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 the parameters once means that you do not get 322 twice.

This algorithm still outputs rotations when there are no unique elements, for example. for [1,1,2,2] it outputs [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 permutations without having to go through after that to remove cyclic rotations?

If not, what is the most effective way to remove cyclic rotations?

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

+5
source share
4 answers

Think about testing each of the derived permutations, look for a cyclic rotation that is “lexically” earlier than the one you have. If it is, do not return it - it will be indicated elsewhere.

"" , , . , , , . , , , . , . (, [1,2,2,1] - [1,1,2,2], [2,2,1,1] [2,1,1,2 ]).

, ... O (n!), , , " ", , (n-1)! .

// 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)
+5

, , . 1,2,...,n, 1,2,...,n-1 n . . , n=4

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

, 1,2,3,4 .

, ( ), . n ( 4 ) . - n ( 4 ).

Lyndon

+3

itertools.permutations , set(), . , O (n!). , , ( itertools.permutations). .

1: . [1, 1, 2, 2] [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

2: itertools.permutations, , set.

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

3: , , (-, ).

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

4: , .

perm = perm.difference(cycles)

, . / .

+1

, 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;

vector, Permutation:

typedef vector<unsigned int> Permutation;

, , :

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

typedef a set, :

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations;

:

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;
}

:

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

CompareCyclicPermutationsEqual. ostream& operator<<(ostream& os, const Permutation& permutation).

+1

More articles:


All Articles