realizar - ¿Cómo generar permutaciones de array en python?

permutation python

Question

Tengo una matriz de 27 elementos, y no quiero generar todas las permutaciones de la matriz (27!) Necesito 5000 permutaciones elegidas al azar, cualquier sugerencia será útil ...

Answer 1

Es posible que desee la función itertools.permutations (). Tienes que amar ese módulo itertools!

NOTA: Nuevo en 2.6

Answer 2

Para generar una permutación, use random.shuffle y almacene una copia del resultado. Repita esta operación en un bucle y cada vez verifique si hay duplicados (aunque probablemente no habrá ninguno). Una vez que tenga 5000 elementos en su conjunto de resultados, deténgase.

Para abordar el punto en el comentario, el módulo aleatorio de Python se basa en el Mersenne Twister y tiene un período de 2**19937-1 , ¡que es considerablemente mayor que 27! por lo que debe ser adecuado para su uso.

Answer 3

Puedes intentar implementar las recetas de random_permutation random_permutation . Por conveniencia, uso una biblioteca de terceros, more_itertools , que implementa esta receta para nosotros:

import more_itertools as mit

iterable = range(27)
mit.random_permutation(iterable)
# (24, 3, 18, 21, 17, 22, 14, 15, 20, 8, 4, 7, 13, 6, 25, 5, 12, 1, 9, 19, 23, 11, 16, 0, 26, 2, 10)

Se crea una permutación aleatoria para cada llamada de la función. Podemos hacer un generador que produzca estos resultados para n llamadas. Implementaremos este generador y demostraremos resultados aleatorios con un ejemplo abreviado:

def random_permute_generator(iterable, n=10):
    """Yield a random permuation of an iterable n times."""
    for _ in range(n):
        yield mit.random_permutation(iterable)

list(random_permute_generator(range(10), n=20))
# [(2, 7, 9, 6, 5, 0, 1, 3, 4, 8),
#  (7, 3, 8, 1, 2, 6, 4, 5, 9, 0),
#  (2, 3, 1, 8, 7, 4, 9, 0, 6, 5),
#  (0, 5, 6, 8, 2, 3, 1, 9, 4, 7),
#  (0, 8, 1, 9, 4, 5, 7, 2, 3, 6),
#  (7, 2, 5, 8, 3, 4, 1, 0, 9, 6),
#  (9, 1, 4, 5, 8, 0, 6, 2, 7, 3),
#  (3, 6, 0, 2, 9, 7, 1, 4, 5, 8),
#  (8, 4, 0, 2, 7, 5, 6, 1, 9, 3),
#  (4, 9, 0, 5, 7, 1, 8, 3, 6, 2)
#  ...]

Para su problema específico, sustituya el iterable y el número de llamadas n con los valores apropiados, por ejemplo, random_permute_generator(iterable, n=5000) .

Consulte también la documentación de more_itertools para obtener más información sobre esta herramienta.

Detalles

Para aquellos interesados, aquí está la receta real.

De las recetas de itertools :

def random_permutation(iterable, r=None):
    "Random selection from itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))

Answer 4

itertools.permutations . Es un generador, por lo que no creará la lista completa de permutaciones. Podrías saltar al azar hasta que tengas 5000.

Answer 5

# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
    for i in range(len(alist)-1):
        apermindex, j = divmod(apermindex, len(alist)-i)
        alist[i], alist[i+j] = alist[i+j], alist[i]
    return alist

Uso: perm_given_index([''a'',''b'',''c''], 3)

Esto usa el código de Lehmer para la permutación ya que los valores de j coinciden con eso.

Answer 6

import random

perm_list = []

for i in range(5000):
    temp = range(27)
    random.shuffle(temp)
    perm_list.append(temp)

print(perm_list)

10888869450418352160768000000 Me encantan los números grandes! :)

Y

10888869450418352160768000001 es PRIME !!

EDITAR:

#with duplicates check as suggested in the comment

perm_list = set()
while len(perm_list)<5000:
    temp = range(27)
    random.shuffle(temp)
    perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?

print perm_list

ADVERTENCIA: ¡Esto nunca se detendrá si RNG es malo!