Ho questo problema:
Immagina di avere un vettore V, numeri interi da 0 a 70000 - ordinati in ordine crescente Ora hai una permutazione P di quel vettore. Quindi fai V [P] "mischiare" il vettore. Se continui a fare V [P] (P non cambia mai), V verrà eventualmente ordinato di nuovo in ordine crescente?
C'è un modo in cui potresti sapere, a priori, come potrebbe essere necessario un rimescolamento?
Dato che il sistema ha un numero finito di stati possibili (70000!), le applicazioni successive dell'operazione P devono alla fine rivisitare qualche stato. E poiché P è reversibile, la sequenza non può entrare in un ciclo che non include lo stato iniziale.
Questo basta per dimostrare che il vettore verrà nuovamente ordinato entro 70000! passi.
Ora guarda P . (Vorrei sapere se ci fosse qualche terminologia matematica e / o simboli standard per questo, ma semplicemente sopportare me.) P porterà un elemento attraverso un circuito e tornerà al suo punto di partenza con un certo periodo. Tutti gli elementi sul circuito hanno lo stesso periodo. Ad esempio, se P è [2 3 1 4] , la sequenza appare come
ABCD
BCAD
CABD
ABCD
Gli elementi {1,2,3} hanno il periodo 3 e {4} il periodo 1.
Ora guarda P = [2 3 1 5 4] :
ABCDE
BCAED
CABDE
ABCED
BCADE
CABED
ABCDE
Gli elementi {1,2,3} hanno periodo 3, {4,5} hanno periodo 2, e il periodo dell'intera permutazione è il minimo comune multiplo di quei periodi , cioè 6 .
Questo ci dice quanto tempo impiegherà un P per restituire il vettore allo stato originale. Quindi qual è il periodo più lungo che può avere una permutazione di N elementi? Dobbiamo suddividere N in un 1 , un 2 , un 3 , ... tale che Σa k = N e LCD (a k ) è massimizzato. Questo è un problema interessante e non è immediatamente ovvio per me quale sia la risposta ...
Poiché "shuffling" è (per definizione) casuale e non ha memoria delle esecuzioni precedenti (per produrre sempre nuove permutazioni), non si può essere certi di raggiungere lo stato ordinato. Molto meno sapere quante ripetizioni potresti aver bisogno.
Leggi altre domande sui tag sorting