python shuffle tale che la posizione non si ripeterà mai

Question

Mi piacerebbe fare un casuale shuffle di una lista ma con una condizione: un elemento non può mai essere nella stessa posizione originale dopo lo shuffle.

Esiste un modo per eseguire tali operazioni in Python per un elenco?

Esempio:

list_ex = [1,2,3] 

ciascuna delle seguenti liste mescolate dovrebbe avere la stessa probabilità di essere campionato dopo il riordino:

list_ex_shuffled = [2,3,1] 
list_ex_shuffled = [3,1,2] 

ma le permutazioni [1,2,3], [ 1,3,2], [2,1,3] e [3,2,1] non sono consentiti poiché tutti ripetono una delle posizioni degli elementi.

NOTA: ogni elemento in list_ex è un ID univoco. Non è consentita la ripetizione dello stesso elemento.

Qualche idea? Grazie!

Answer 1

Randomize in un ciclo e mantenere respingendo i risultati fino a quando la condizione è soddisfatta:

import random 

def shuffle_list(some_list): 
    randomized_list = some_list[:] 
    while True: 
     random.shuffle(randomized_list) 
     for a, b in zip(some_list, randomized_list): 
      if a == b: 
       break 
     else: 
      return randomized_list 

Answer 2

Si potrebbe generare tutte le possibili stropiccii validi:

>>> list_ex = [1,2,3] 
>>> import itertools 

>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)), 
...      itertools.permutations(list_ex, len(list_ex)))) 
[(2, 3, 1), (3, 1, 2)] 

per qualche altra sequenza:

>>> list_ex = [7,8,9,0] 
>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)), 
...      itertools.permutations(list_ex, len(list_ex)))) 
[(8, 7, 0, 9), (8, 9, 0, 7), (8, 0, 7, 9), (9, 7, 0, 8), (9, 0, 7, 8), (9, 0, 8, 7), (0, 7, 8, 9), (0, 9, 7, 8), (0, 9, 8, 7)] 

Si potrebbe anche fare di questo un po 'più efficiente cortocircuitando l'iteratore se si desidera solo un risultato:

>>> list_ex = [1,2,3] 
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)), 
...      itertools.permutations(list_ex, len(list_ex))) 
>>> next(i) 
(2, 3, 1) 

Ma, non sarebbe un random scelta. Avresti per generare tutti loro e scegliere uno per essere un risultato effettivo casuale:

>>> list_ex = [1,2,3] 
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)), 
...      itertools.permutations(list_ex, len(list_ex))) 
>>> import random 
>>> random.choice(list(i)) 
(2, 3, 1) 

Answer 3

Ecco un'altra opinione su questo. Puoi scegliere una soluzione o un'altra in base alle tue esigenze. Questo non è un solo rivestimento, ma mescola gli indici degli elementi invece degli elementi stessi. Pertanto, l'elenco originale può avere valori o valori duplicati di tipi che non possono essere confrontati o che possono essere costosi da confrontare.

#! /usr/bin/env python 
import random 

def shuffled_values(data): 
    list_length = len(data) 
    candidate = range(list_length) 
    while True: 
     random.shuffle(candidate) 
     if not any(i==j for i,j in zip(candidate, range(list_length))): 
      yield [data[i] for i in candidate] 

list_ex = [1, 2, 3] 
list_gen = shuffled_values(list_ex) 
for i in range(0, 10): 
    print list_gen.next() 

Questo dà:

[2, 3, 1] 
[3, 1, 2] 
[3, 1, 2] 
[2, 3, 1] 
[3, 1, 2] 
[3, 1, 2] 
[2, 3, 1] 
[2, 3, 1] 
[3, 1, 2] 
[2, 3, 1] 

Se list_ex è [2, 2, 2], questo metodo di tenere cedere [2, 2, 2] più e più volte. Le altre soluzioni ti daranno delle liste vuote. Non sono sicuro di cosa vuoi in questo caso.

Answer 4

Descriverei tali mescolanze come "permutazioni senza punti fissi". Sono anche noti come derangements.

La probabilità che una permutazione casuale sia uno squilibrio è di circa 1/e (divertente da dimostrare). Questo è vero per quanto sia lunga la lista. Quindi un algoritmo ovvio per dare un disallineamento casuale è quello di mescolare le carte normalmente, e continuare a mescolare finché non si ha un disallineamento. Il numero previsto di mescolanze necessarie è di circa 3, ed è raro che dovrai mischiare più di dieci volte.

(1-1/e)**11 < 1% 

---

Supponiamo che ci sono n persone ad un partito, ognuno dei quali ha portato un ombrello. Alla fine della festa, ogni persona prende un ombrello a caso dal cesto. Qual è la probabilità che nessuno abbia il proprio ombrello?

Answer 5

Ecco un altro algoritmo. Prendere le carte a caso Se la tua carta ith è la carta i, rimettila e riprova. Unico problema, cosa succede se quando arrivi all'ultima carta è quella che non vuoi. Scambialo con uno degli altri.

Penso che sia giusto (uniformemente casuale).

import random 

def permutation_without_fixed_points(n): 
    if n == 1: 
     raise ArgumentError, "n must be greater than 1" 

    result = [] 
    remaining = range(n) 

    i = 0 
    while remaining: 
     if remaining == [n-1]: 
      break 

     x = i 
     while x == i: 
      j = random.randrange(len(remaining)) 
      x = remaining[j] 

     remaining.pop(j) 
     result.append(x) 

     i += 1 

    if remaining == [n-1]: 
     j = random.randrange(n-1) 
     result.append(result[j]) 
     result[j] = n 

    return result