Python shuffle takie, że pozycja nigdy się nie powtórzy

Question

Chciałbym losowo przetasować listę, ale z jednym warunkiem: element nie może być nigdy w tej samej oryginalnej pozycji po shuffle.

Czy istnieje jednoliniowy sposób na takie w python dla listy?

przykład:

list_ex = [1,2,3] 

każdego z następujących list tasuje powinien mieć takie samo prawdopodobieństwo zostania próbki po tłumie:

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

ale permutacji [1,2,3], [ 1,3,2], [2,1,3] i [3,2,1] są niedozwolone, ponieważ wszystkie z nich powtarzają jedną z pozycji elementów.

UWAGA: Każdy element w klasie list_ex jest unikalnym identyfikatorem. Nie można powtórzyć tego samego elementu.

Wszelkie pomysły? dzięki!

Answer 1

Randomize w pętli i zachować odrzucając wyniki dopóki warunek jest spełniony:

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

Można wygenerować wszystkie możliwe poprawne shufflings:

>>> 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)] 

dla innych sekwencji:

>>> 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)] 

Można również zrobić to nieco bardziej wydajny przez zwarcie iteracyjnej jeśli tylko chcesz jeden wynik:

>>> 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) 

Ale nie byłby to losowy wybór. Trzeba by wygenerować wszystkie z nich i wybrać jedną, aby była ona rzeczywisty wynik przypadkowy:

>>> 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

Oto inne podejście do tego. Możesz wybrać jedno lub drugie rozwiązanie w zależności od potrzeb. Nie jest to jedna liniówka, ale tasuje wskaźniki elementów zamiast samych elementów. Tak więc oryginalna lista może zawierać zduplikowane wartości lub wartości typów, których nie można porównać lub które mogą być drogie w porównaniu.

#! /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() 

Daje:

[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] 

Jeśli list_ex jest [2, 2, 2], metoda ta będzie na bieżąco otrzymując [2, 2, 2] kółko. Inne rozwiązania dadzą ci puste listy. Nie jestem pewien, czego chcesz w tym przypadku.

Answer 4

Opisałbym takie tasowanie jako "permutacje bez stałych punktów". Są również znane jako derangements.

Prawdopodobieństwo, że permutacja losowa jest zakłóceniem, wynosi w przybliżeniu 1/e (zabawa dowodzi). Jest to prawda, jednak długo na liście. Zatem oczywistym algorytmem, który daje losowe zakłócanie, jest normalne tasowanie kart i kontynuowanie tasowania, aż do wystąpienia obłędu. Spodziewana liczba niezbędnych tasowań wynosi około 3, a rzadko trzeba potasować więcej niż dziesięć razy.

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

---

Załóżmy, że istnieją n osób na imprezie, z których każdy wniósł parasol. Na zakończenie imprezy każda osoba bierze losowo parasol z koszyka. Jakie jest prawdopodobieństwo, że nikt nie ma własnego parasola?

Answer 5

Oto kolejny algorytm. Weź losowo karty. Jeśli twoją kartą jest karta i, odłóż ją i spróbuj ponownie. Tylko problem, co jeśli, kiedy dojdziesz do ostatniej karty, to jest to, czego nie chcesz. Zamień go z jednym z pozostałych.

Myślę, że jest to uczciwe (jednolicie losowe).

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