python - array - shuffle list c#

python shuffle tal posición nunca se repetirá

Question

Me gustaría hacer una mezcla aleatoria de una lista pero con una condición: un elemento nunca puede estar en la misma posición original después de la mezcla.

¿Hay una forma de hacer una línea en python para una lista?

Ejemplo:

list_ex = [1,2,3]

cada una de las siguientes listas mezcladas debería tener la misma probabilidad de ser muestreada después de la mezcla:

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

pero las permutaciones [1,2,3], [1,3,2], [2,1,3] y [3,2,1] no están permitidas ya que todas ellas repiten una de las posiciones de los elementos.

NOTA: cada elemento en list_ex es una identificación única. No se permite la repetición del mismo elemento.

¿Algunas ideas? ¡Gracias!

Answer 1

Aleatorice en un bucle y siga rechazando los resultados hasta que se cumpla su condición:

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

Aquí hay otra opinión sobre esto. Puede elegir una solución u otra dependiendo de sus necesidades. Este no es un trazador de líneas, sino que mezcla los índices de los elementos en lugar de los elementos mismos. Por lo tanto, la lista original puede tener valores duplicados o valores de tipos que no se pueden comparar o que pueden ser caros de comparar.

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

Esto da:

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

Si list_ex es [2, 2, 2] , este método seguirá cediendo [2, 2, 2] una y otra vez. Las otras soluciones te darán listas vacías. No estoy seguro de lo que quieres en este caso.

Answer 3

Podrías generar todos los cambios válidos posibles:

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

Para alguna otra secuencia:

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

También podría hacerlo un poco más eficiente al cortocircuitar el iterador si solo quiere un resultado:

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

Pero, no sería una elección aleatoria . Tendría que generarlos todos y elegir uno para que sea un resultado aleatorio real:

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

Aquí hay otro algoritmo. Toma cartas al azar. Si su iésima tarjeta es la tarjeta i, vuelva a colocarla y vuelva a intentarlo. El único problema, ¿qué pasa si cuando llegas a la última carta es la que no quieres? Cambiarlo con uno de los otros.

Creo que esto es justo (uniformalmente aleatorio).

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

Answer 5

Describiría esos cambios aleatorios como ''permutaciones sin puntos fijos''. También se conocen como trastornos .

La probabilidad de que una permutación aleatoria sea un trastorno es aproximadamente 1 / e (es divertido de probar). Esto es cierto sin importar la longitud de la lista. Por lo tanto, un algoritmo obvio para dar una alteración aleatoria es mezclar las cartas normalmente y seguir barajando hasta que tengas un trastorno. El número esperado de mezclas necesarias es de aproximadamente 3, y es raro que tengas que barajar más de diez veces.

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

Supongamos que hay n personas en una fiesta, cada una de las cuales trajo un paraguas. Al final de la fiesta, cada persona toma un paraguas al azar de la canasta. ¿Cuál es la probabilidad de que nadie tenga su propio paraguas?