Generazione di tutte le permutazioni escludendo le rotazioni cicliche

Question

Così ho bisogno di un algoritmo per generare tutte le permutazioni di una lista di numeri esclusi rotazioni cicliche (ad esempio [1,2,3] == [2,3,1] == [3,1,2]).

Quando c'è almeno un numero univoco nella sequenza è abbastanza semplice, estrarre quel numero univoco, generare tutte le permutazioni dei numeri rimanenti (ma con una piccola modifica all'algoritmo di permutazioni "standard") e aggiungere il numero univoco in primo piano.

Per generare le permutazioni che ho trovato che è necessario modificare il codice permutazioni a:

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 

Solo utilizzando ogni numero univoco nelle opzioni significa che una volta che non si ottiene 322 due volte.

Questo algoritmo genera ancora rotazioni quando non ci sono elementi univoci, ad es. per [1,1,2,2] produrrebbe [1,1,2,2], [1,2,2,1] e [1,2,1,2] e le prime due sono rotazioni cicliche.

Quindi esiste un algoritmo efficiente che mi consenta di generare tutte le permutazioni senza dover passare in seguito per rimuovere le rotazioni cicliche?

In caso contrario, quale sarebbe il modo più efficiente per rimuovere le rotazioni cicliche?

NOTA: questo è non con Python, ma piuttosto C++.

Answer 1

Pensa a testare ciascuna delle permutazioni che emetti, cercando una rotazione ciclica che sia "lessicalmente" prima di quella che hai. Se ce n'è uno, non restituirlo: sarà enumerato da qualche altra parte.

Scegliere un elemento "unico", se esistente, consente di ottimizzare. Sai se aggiusti il ​​primo elemento, ed è unico, allora non puoi averlo duplicato con una rotazione. D'altra parte, se non esiste un elemento così unico, basta scegliere quello che si verifica meno. In questo modo devi solo controllare le rotazioni cicliche che hanno quel primo elemento. (Esempio, quando generi [1,2,2,1] - devi solo controllare [1,1,2,2], non [2,2,1,1] o [2,1,1,2 ]).

---

OK, pseudocodice ... chiaramente O (n!), E sono convinto che non c'è modo più intelligente, dal momento che il caso "tutti i simboli diversi" ha ovviamente per tornare (n-1)! elementi.

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

Questa soluzione implicherà un po 'di utilizzo di itertools.permutations, set() e alcune buone differenze di set di stile. Tenete a mente, il tempo di esecuzione per trovare una permutazione sarà comunque O (n!). La mia soluzione non lo farà in linea, ma lo potrebbe essere una soluzione molto più elegante che ti permette di farlo (e non coinvolge itertools.permutations). Per questo scopo, questo è il modo semplice per eseguire l'operazione.

Passo 1: Algoritmo per generare cicli, utilizzando il primo elemento fornito. Per un elenco [1, 1, 2, 2], questo ci darà [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 

Fase 2: Importazione itertools.permutations a darci le permutazioni, in primo luogo, poi impostare i propri risultati in un set.

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

Fase 3: Utilizzo del generatore di darci il nostro set, con i cicli (qualcosa che vogliamo liberarci di).

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

Passaggio 4: Applica la differenza di set a ciascuno e i cicli vengono rimossi.

perm = perm.difference(cycles) 

Speriamo che questo ti possa aiutare. Sono aperto a suggerimenti e/o correzioni.

Answer 3

Per il caso di permutazioni in cui tutti i numeri sono distinti, questo è semplice. Dire che i numeri sono 1,2,...,n, quindi generare tutte le permutazioni di 1,2,...,n-1 e bastone n nella parte anteriore. Ciò fornisce tutte le permutazioni delle rotazioni cicliche del modulo completo. Ad esempio, con n=4, si farebbe

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

Questo assicura che una certa rotazione ciclica di ogni permutazione di 1,2,3,4 appare esattamente una volta nella lista.

Per il caso generale in cui si desidera le permutazioni di un multiset (sono consentite voci ripetute), è possibile utilizzare un trucco simile. Rimuovere tutte le istanze della lettera più grande n (simile a ignorare lo 4 nell'esempio precedente) e generare tutte le permutazioni del multiset rimanente. Il passaggio successivo consiste nel reinserire gli n nelle permutazioni in modo canonico (simile a inserire 4 all'inizio dell'esempio precedente).

Questo è davvero solo un caso di trovare tutto Lyndon words per generare necklaces

Answer 4

Prima ti faccio vedere i contenitori e gli algoritmi saremo in 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; 

Successivo nostro vector che rappresenterà la Permutation:

typedef vector<unsigned int> Permutation; 

Abbiamo bisogno di un oggetto di confronto per verificare se sussiste er una permutazione è una rotazione:

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

E typedef un set che utilizza l'oggetto di confronto ciclico:

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations; 

Allora la funzione principale è molto semplice:

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

uscita:

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

Non ho ancora implementato CompareCyclicPermutationsEqual. Inoltre, è necessario implementare ostream& operator<<(ostream& os, const Permutation& permutation).