Генерация всех перестановок, кроме циклических вращений

Question

Поэтому мне нужен алгоритм для генерации всех перестановок списка чисел, кроме циклических вращений (например, [1,2,3] == [2,3,1] == [3,1, 2]).

Когда в последовательности есть хотя бы 1 уникальный номер, он довольно прост, уберите этот уникальный номер, сгенерируйте все перестановки оставшихся чисел (но с небольшой модификациейстандартный алгоритм перестановок) и добавьте уникальный номер впереди.

Для генерации перестановок я обнаружил, что необходимо изменить код перестановок на:

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

Только с использованием каждогоуникальное число в опциях один раз означает, что вы не получите 322 дважды.

Этот алгоритм по-прежнему выводит повороты, когда нет уникальных элементов, например, для [1,1,2,2] он будет выводить [1,1,2,2], [1,2,2,1] и [1,2,1,2] и первые два являются циклическими вращениями.

Так есть ли эффективный алгоритм, который позволил бы мнегенерировать все перестановки без необходимости проходить потом, чтобы удалитьциклические вращения?

Если нет, то какой самый эффективный способ удалить циклические вращения?

ПРИМЕЧАНИЕ : это не с использованием Python, а точнее C ++.

Answer 1

Подумайте о тестировании каждой перестановки, которую вы выводите, ища циклическое вращение, которое «лексически» раньше, чем у вас. Если он есть, не возвращайте его - он будет перечислен где-то еще.

Выбор «уникального» первого элемента, если таковой существует, помогает оптимизировать. Вы знаете, что если вы исправите первый элемент, и он уникален, то вы не сможете дублировать его вращением. С другой стороны, если такого уникального элемента нет, просто выберите тот, который встречается меньше всего. Таким образом, вам нужно только проверить циклические вращения, которые имеют этот первый элемент. (Например, когда вы генерируете [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)

Answer 2

Для случая перестановок, где все числа различны, это просто.Скажите, что числа 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 в начале в приведенном выше примере).

На самом деле это всего лишь случай нахождения всех слов Линдона для генерации ожерелий

Answer 3

Сначала я покажу контейнеры и алгоритмы, которыми мы будем 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).

Answer 4

Это решение будет включать в себя немного itertools.permutations использования, set() и некоторую хорошую старомодную разность наборов.Имейте в виду, что время нахождения перестановки все равно будет O (n!).Мое решение также не будет делать это in-line, но может быть гораздо более элегантным решением, которое позволяет вам сделать это (и не включает 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)

Надеюсь, это поможет вам.Я открыт для предложений и / или исправлений.