Alla ricerca di un algoritmo per sputare fuori una sequenza di numeri in una (pseudo) ordine casuale

StackOverflow https://stackoverflow.com/questions/732700

Domanda

Supponiamo che io sono una sequenza di numeri: {N, n + 1, n + 2, ... n + m}

senza memorizzare i numeri prima del tempo che voglio creare una funzione f (), che data la successione {1,2,3, ... m} sarà sputare fuori la serie originale in un caso (o almeno pseudo casuale) ordine.

Per esempio assumere la mia sequenza è {10, 11, 12, 13, 14, 15, 16, 17} 

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

A un certo punto, in passato un collega mi ha mostrato un algoritmo matematico che è stato in grado di fare questo, ma ho dimenticato da quasi tutto su di esso diverso da quello che esisteva. Mi ricordo che si doveva avere la sequenza in anticipo, e generare alcune costanti della sequenza che sono stati utilizzati nella funzione. E per coloro che chiedono, ho purtroppo perso il contatto con quel collega di lavoro.

Questa domanda di href="https://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats"> sembra vicino a quello che voglio, ma non sono sicuro se le risposte mi permettono di vincolare l'output in una sequenza specifica prima del tempo.

Modifica

Per chiarire un po 'di più non voglio memorizzare la sequenza originale, o la sequenza mescolate. Voglio generare una funzione f () dalla sequenza originale.

Ciò che è frustrante è che ho visto questo, non riesco proprio a ricordare abbastanza per trovare di nuovo con Google.

L'algoritmo di Fisher-Yates è grande per permutando o mischiare un mazzo, ma non è quello che sto cercando.

È stato utile?

Soluzione

C'è una semplice funzione che genera una permutazione di [0..m-1] per un dato m. Basta scegliere un numero k, relativamente privilegiata per m e lasciare f(i)=(k*i) mod m. Questo genera sempre una permutazione (senza ripetizioni su 0<=i<m). Funziona meglio se k è più grande di m.

Per esempio, m = 20, sia K = 137 (codice Python, % significa modulo): 

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

Questo è molto semplice PRNG, garanzie sulle sue proprietà statistiche.

Altri suggerimenti

La tua domanda è un po 'di confusione, in quanto sembra che si desidera ottenere tutta la sequenza originale di nuovo, ma poi si deve sia la mappatura 4 e da 8 a 10, e la mappatura nulla a 12.

Se in realtà voleva dire che per essere un 1: 1 mapping, allora quello che stai cercando è una permutazione casuale del set originale. Ci sono modi per farlo con o senza raccogliere il primo set (ma avrete bisogno di qualcosa che lo genera, o tenere traccia di dove siete).

Si noti inoltre che n non è importante. È sempre possibile utilizzare 0,1,2, ... m e quindi aggiungere n a tutto ciò, se necessario.

Supponendo che ho interpretato questo correttamente e si sono effettivamente alla ricerca di un algoritmo shuffle (cioè permutazione casuale, chiamato mescola per analogia ai mischiare un mazzo di carte), hanno uno sguardo al Fisher-Yates

[Modifica] Ok, in base alla aggiornamento, il problema si faccia è questa: Non si vuole codificare la permutazione in modo esplicito, ma è necessario codificare in qualche modo per costruire f. Il modo più semplice è solo quello di archiviare gli indici permutati in un array, ma se non si vuole fare che per qualche motivo (ad esempio troppo grande), è possibile codificare in vari modi. Non c'è il pranzo libero, però, in quanto vi sono informazioni teorico limiti su quanto sia semplice questo può essere. Ad ogni modo, è possibile ottenere alcune idee da guardare i lavori sulla "permutazioni di codifica", per esempio qualcosa come questo documento

Ecco alcuni pseudocodice nella mia lingua inventata: 

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray

aggiungere i valori iniziali per una lista.
quindi, utilizzare un numero casuale per scegliere un nuovo valore di indice nella gamma di dimensioni attuali della lista.
utilizzare tale indice per selezionare e quindi rimuovere il numero dalla lista.

come qualcuno già sottolineato, questo è simile ad avere un mazzo di carte, e quindi rimuovendo una carta a caso alla volta.

Se si desidera un 1:. Mappatura 1, andare con Fisher-Yates come detto in altre risposte

Se non si cura di mappatura 1: 1, e basta tutti i valori risultanti di essere dalla sequenza data (con la possibilità di ripetizioni), quindi è possibile utilizzare una funzione casuale con un intervallo specificato.

Per esempio, in C ++, si potrebbe usare rand () nel seguente modo - 

result = rand() % (m+1) + n

Così, per il tuo esempio, 

result = rand() % 8 + 10

produrrebbe un intero compreso tra 10 e 17.

Puoi montare un polinomiale alla sequenza selezionata; Direi che è quello che il vostro collega vi ha mostrato. Non sarà risparmiare spazio rispetto ad appena ricordare la permutazione, però.

È possibile generare una permutazione dei primi n numeri interi utilizzando un cifrario a blocchi e XOR piegatura, come per la mia risposta precedente .

Non è possibile per restituire i valori senza memorizzare i risultati della funzione originale da qualche parte. Ragionamento:

Il generatore di numeri casuali che si dice di restituire questi valori dalla sequenza originale:. 5 °, 11 °, 3 °

Quindi si salta i primi quattro valori, restituire il 5 °, saltare un altro 5, restituire il 11 ° ... ora come si fa a restituire il 3 ° senza salvarlo da qualche parte?

La cosa più vicina si può farla franca è la creazione di una lista e aggiungere tutti i valori che si saltellate ma quel suono molto difficile e probabilmente non vale la pena. Inoltre, sarebbe stato molto lento nel caso in cui l'algoritmo rimescolamento restituisce un molto grande e quindi un valore molto piccolo (nel qual caso si sarebbe effettivamente copiare la maggior parte dei valori nella lista, prima che si vuole evitare).

Io resto il mio caso.

Your input è descritto da f(x) => x + 9, o più in generale f(x) => n - 1 + x come x inizia da 1.

Si collega un'altra domanda che descrive una funzione che r(x) mappe x per un valore mescolate, 0 <= r(x) <= m.

in modo f(r(x) + 1) o (r(x) + n)should ti danno il valore che si desidera.

Per i piccoli m, si dovrebbe anche essere in grado di trovare i semi di un generatore di numeri casuali standard con pista ed errore che poi generano m+1 valori distinti, quando prese m+1 mod se non si vuole codificare il proprio generatore.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top