Come mescolare un array in modo che tutti gli elementi cambino la loro posizione

Ho bisogno di mescolare un array in modo che tutti gli elementi dell'array cambino la loro posizione. Dato un array [0,1,2,3] sarebbe ok per ottenere [1,0,3,2] o [3,2,0,1] ma non [3,1,2,0] (perché 2 lasciato invariato). Suppongo che l'algoritmo non sia specifico della lingua, ma nel caso, ne ho bisogno nel programma C++ (e non posso usare std::random_shuffle a causa del requisito aggiuntivo).Come mescolare un array in modo che tutti gli elementi cambino la loro posizione

fonte

2013-02-26 Nick

Avete dei requisiti di memoria? È possibile creare un nuovo array della stessa dimensione del primo e quindi spostare semplicemente ciascun elemento in array1 in una nuova posizione casuale in array2. Se il valore è già stato impostato, riprova. Forza molto bruta. – Liron

Un altro approccio: iniziare con l'indice 0 e scambiarlo con un altro indice casuale. Mantieni un elenco di tutti gli indici che sono già stati scambiati. Scorrere l'elenco, scambiando solo con elementi non aggiornati. – Liron

L'approccio più semplice, anche se completamente non casuale, sposta tutti gli elementi dell'array in base alle posizioni x. Dovrebbe essere facile da fare in qualsiasi lingua, basta creare un nuovo array, copiare il primo gruppo in un offset, quindi copiare il resto all'inizio. –

For each element e 
    If there is an element to the left of e 
     Select a random element r to the left of e 
      swap r and e

Ciò garantisce che ciascun valore non è nella posizione in cui è stato avviato, ma non garantisce che ogni valore cambi se sono presenti duplicati.

fonte

2013-02-26 18:17:16

Stai facendo il contrario per sto bene? –

In entrambi i casi funziona bene –

Credo che sia una variante di Fisher-Yates shuffle, noto come [l'algoritmo di Sattolo] (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). – jrok

Non sarà molto casuale, ma è possibile ruotare tutti gli elementi almeno una posizione:

std::rotate(v.begin(), v.begin() + (rand() % v.size() - 1) + 1, v.end());

Se v era {1,2,3,4,5,6,7,8,9} all'inizio, poi dopo la rotazione sarà, ad esempio: {2,3,4,5,6,7,8,9,1} oppure {3,4,5,6,7,8,9,1,2}, ecc.

Tutti gli elementi dell'array cambieranno posizione.

fonte

2013-02-26 18:14:54 piokuc

C'è un problema con questa soluzione? – piokuc

Questo non mescola l'array. Dà un risultato prevedibile. – 0x499602D2

+1. Soluzione semplice e correttaNon vedo alcun motivo per includere la casualità nella soluzione, non ha nulla a che fare con il problema dichiarato. – SomeWittyUsername

Che dire di questo?

allocare una matrice che contiene i numeri da 0 a arrayLength-1
Mescola matrice
Se non v'è alcun elemento dell'array con indice uguale al valore di, passare al punto 4; altrimenti ripetere dal passaggio 2.
Utilizzare i valori di array shuffled come indici per l'array.

fonte

2013-02-26 18:18:12

Questo sembra carino perché è possibile esternalizzare lo shuffling a 'std :: random_shuffle' e il rimescolamento sembra la parte più difficile. – CallMeNorm

Ho una specie di idea nella speranza che sia adatta alla vostra applicazione. Avere un altro contenitore e questo contenitore sarà una "mappa (int, vector (int))". L'elemento chiave mostrerà l'indice e il secondo elemento il vettore conterrà i valori già utilizzati.

Ad esempio per il primo elemento si utilizzerà la funzione rand per trovare quale elemento della matrice si dovrebbe usare. Si verificherà la struttura della mappa se questo elemento dell'array è stato utilizzato per questo indice.

fonte

2013-02-26 18:38:51

Mi dispiace per "map (int, vector (int))" Non riuscivo a capire come usare "<" invece "(" –

Come mescolare un array in modo che tutti gli elementi cambino la loro posizione

risposta

Problemi correlati