wygenerowanie wszystkich permutacji wyłączając cyklicznego obrotów

Question

więc potrzeba algorytm w celu wygenerowania wszystkich permutacji listy numerów wyjątkiem obrotów cykliczne (np [1,2,3] == [2,3,1] == [3,1,2]).

Gdy istnieje co najmniej jeden unikalny numer w sekwencji, który jest dość prosty, wyjmij ten unikalny numer, wygeneruj wszystkie permutacje pozostałych liczb (ale z niewielką modyfikacją "standardowego" algorytmu permutacji) i dodaj unikalny numer z przodu.

do generowania permutacji odkryłem, że jest to konieczne, aby zmienić kod permutacji do:

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 

Tylko pomocą każdego unikalnego numeru w opcjach raz oznacza, że ​​nie dostaniesz 322 razy.

Algorytm ten nadal generuje obroty, gdy nie ma żadnych unikatowych elementów, np. dla [1,1,2,2] wyniósłby [1,1,2,2], [1,2,2,1] i [1,2,1,2], a pierwsze dwa to rotacje cykliczne.

Czy istnieje skuteczny algorytm, który pozwoliłby mi generować wszystkie permutacje bez konieczności późniejszego usuwania cyklicznych obrotów?

Jeśli nie, jaki byłby najskuteczniejszy sposób na usunięcie cyklicznych obrotów?

UWAGA: To jest nie przy użyciu Python, ale raczej C++.

Answer 1

Pomyśl o przetestowaniu każdej z wydanych permutacji, szukając cyklicznej rotacji, która jest "leksykalna" wcześniej niż ta, którą masz. Jeśli istnieje, nie zwracaj go - zostanie on wyliczony gdzie indziej.

Wybór "unikalnego" pierwszego elementu, o ile taki istnieje, pomaga zoptymalizować. Wiesz, jeśli naprawisz pierwszy element i będzie on unikatowy, wtedy nie będzie możliwe jego powielenie z rotacją. Z drugiej strony, jeśli nie ma takiego unikalnego elementu, po prostu wybierz ten, który występuje najmniej. W ten sposób wystarczy sprawdzić cykliczne rotacje, które mają ten pierwszy element. (Przykład: kiedy generujesz [1,2,2,1] - musisz tylko sprawdzić [1,1,2,2], a nie [2,2,1,1] lub [2,1,1,2] ]).

---

OK, pseudokod ... wyraźnie O (n!), I jestem przekonany, że nie ma lepszy sposób, ponieważ sprawa "wszystkie symbole różnych" oczywiście ma powrócić (n-1)! elementy.

// 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

Rozwiązanie to będzie wymagało użycia pewnej liczby urządzeń: itertools.permutations, set() i pewnej dobrej różnicy w ustawieniu "ol". Pamiętaj, że czas potrzebny na znalezienie permutacji nadal będzie O (n!). Moje rozwiązanie również nie będzie działać w trybie on-line, ale może być może być bardziej eleganckie rozwiązanie, które pozwala to zrobić (i nie obejmuje itertools.permutations). W tym celu jest to prosty sposób na wykonanie tego zadania.

Krok 1: Algorytm generowania cykli z wykorzystaniem pierwszego podanego elementu. Dla listy [1, 1, 2, 2] da nam to [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 

Krok 2: Importowanie itertools.permutations dać nam permutacje w pierwszej kolejności, a następnie utworzenie jego wyniki w set.

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

Krok 3: Korzystanie z generatora, aby dać nam nasz własny zestaw, z cyklami (coś chcemy pozbyć się).

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

Krok 4: Zastosuj ustawioną różnicę do każdego i cykle są usuwane.

perm = perm.difference(cycles) 

Mam nadzieję, że to ci pomoże. Jestem otwarty na sugestie i/lub poprawki.

Answer 3

Dla przypadku permutacji, w których wszystkie liczby są różne, jest to proste. Powiedzmy, że liczby są 1,2,...,n, a następnie generują wszystkie permutacje 1,2,...,n-1 i trzymają n z przodu. Daje to wszystkie permutacje pełnego zestawu cyklicznych rotacji modulo. Na przykład, z n=4, byś

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

Gwarantuje to, że niektóre cykliczny obrót każdej permutacji 1,2,3,4 pojawia się tylko raz na liście.

W ogólnym przypadku, w którym chcesz uzyskać permutacje multiset (dozwolone powtarzanie wpisów), możesz użyć podobnej sztuczki. Usuń wszystkie wystąpienia największej litery n (podobnie jak ignorowanie 4 w powyższym przykładzie) i wygeneruj wszystkie permutacje pozostałego multiset. Następnym krokiem jest przeniesienie n s do permutacji w kanoniczny sposób (podobnie jak umieszczenie 4 na początku w powyższym przykładzie).

Jest to naprawdę tylko kwestia znalezienia wszystkich Lyndon words wygenerować necklaces

Answer 4

najpierw pokażę pojemników i algorytmów będziemy 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; 

Następny nasz vector które reprezentują Permutation:

typedef vector<unsigned int> Permutation; 

Potrzebujemy obiektu do porównania, aby sprawdzić ER permutacji jest obrotowa:

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

I typedefset który wykorzystuje cykliczny porównania obiekt:

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations; 

Następnie główną funkcją jest prosty:

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

wyjściowa:

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

Jeszcze nie zaimplementowałem CompareCyclicPermutationsEqual. Ponadto musisz wdrożyć ostream& operator<<(ostream& os, const Permutation& permutation).