Esiste una sequenza di swap in grado di generare tutte le possibili permutazioni?

Question

Si è data una lista di numeri 1, 2, ... ,n - c'è una sequenza di n!-1swap operazioni, che potrebbero generare tutti n! permutazioni della lista in cui swap (i, j) swap elementi a cellule i e j? Che dire del caso generale in cui l'elenco di input non è ordinato per iniziare e/o ci sono ripetizioni nell'elenco?

Contesto: Sto risolvendo un problema in cui il "punteggio" di un array è facile da calcolare se si conosce già il punteggio se 2 elementi vengono scambiati e io voglio forza bruta (usando C++ next_permutation()) tutte le possibili permutazioni.

Answer 1

Certo, ed era noto ai suonatori di campane del 17 ° secolo. Allora, com'è per un po 'di storia combinatoria?

Vedere the Steinhaus Johnson Trotter algorithm o consultare il proprio gruppo di suoneria di cambio locale.

---

Ho fatto un po 'di ricerca sulla seconda parte della domanda, ovvero se è possibile farlo con elementi ripetuti. La risposta, credo, è "sì, ma non così facilmente". Inoltre, non è possibile permutare una lista con elementi ripetuti con swap adiacenti, come si può facilmente vedere per il set {0, 0, 1, 1}. Tuttavia, è possibile con solo singoli swap.

L'approccio di base consiste nell'utilizzare l'algoritmo di base di modifica delle suonerie, ma su gruppi di elementi identici anziché su singoli elementi. Per un gruppo di elementi identici k, è necessario essere in grado di un algoritmo per le combinazioni dell'elenco 0 ^{n- k} (dove n è la dimensione totale del set di base). Esiste un certo numero di tali algoritmi, ma non riesco a trovare nessuno che sia veramente semplice; il più semplice è (in parole povere) per assegnare una direzione al gruppo generale, e anche una direzione per ogni 1 (in modo simile all'algoritmo Shimon Even). Quando si sposta il gruppo a sinistra, l'elemento più a sinistra spazia avanti e indietro; ogni volta che cambia direzione, il prossimo elemento mobile a destra ne esegue uno; ecc. Questo alla fine sposta l'intero gruppo dal lato destro della lista verso il lato sinistro, dopo di che la sua direzione generale viene capovolta e ritorna alla configurazione originale, ora con l'elemento più a destra che conduce gli sweep.

Poiché il numero di inversioni di direzione potrebbe essere anche in questo caso, l'algoritmo di cui sopra potrebbe non tracciare un ciclo di permutazione, ma credo che sia possibile produrre un ciclo utilizzando un algoritmo più sofisticato. In effetti, stai cercando un ciclo hamiltoniano nel grafico indotto da possibili singoli swap da ogni permutazione - una variante del permuteedro - ma, mentre i cicli hamiltoniani esistono, non sono così facili da trovare poiché i grafici sono Abbastanza grande.