Tengo una serie de 27 elementos, y yo no quiero para generar todas las permutaciones de array (27!) Que necesito 5000 permutaciones choosed al azar, cualquier punta que será útil ...cómo generar permutaciones de matriz en python?
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 haya ninguno). Una vez que tenga 5000 elementos en su conjunto de resultados, deténgase.
Para abordar el punto en el comentario, Python random module se basa en la Mersenne Twister y tiene un período de 2**19937-1, que es considerablemente más grande que 27! por lo que debe ser adecuado para su uso.
+1, pero tenga en cuenta que 'random.shuffle' tiene una debilidad seria: el período de la mayoría de los RNG es menor que el número total de permutaciones a medida que _n_ aumenta. Eso significa que casi todas las permutaciones posibles para un _n_ lo suficientemente grande nunca se pueden generar, por lo que esto no es realmente aleatorio. –
De hecho, John. El generador aleatorio de Python tiene un período de 2 ** 19937-1, por lo que probablemente sea lo suficientemente bueno. Otro detalle es que para los verdaderos números aleatorios se necesita una verdadera fuente aleatoria (por ejemplo, de desintegración radiactiva), el módulo aleatorio de Python proporciona solo números pseudoaleatorios. Pero en el uso común cuando la gente dice 'aleatorio' lo que realmente quieren decir es 'pseudoaleatorio', y supongo que esto es lo que significa el afiche aquí. –
+1 ¡Genial! Es un gran dado con 10888869450418352160768000000 la probabilidad de que cualquiera de ellos aparezca es 1/10888869450418352160768000000. ¡Duplica SIN MANERA! –
itertools.permutations. Es un generador, por lo que no creará la lista completa de permutaciones. Puede omitir aleatoriamente hasta obtener 5000.
puede tardar mucho tiempo para hacer uso de este método .... –
Eso no es realmente "aleatoria",! ya que 'itertools' los crea en un orden definido, y hay un número finito de permutaciones. Lo que sería mejor es hacer lo siguiente: (1) determinar ** cuántas ** permutaciones hay (llamar a este número 'N'), (2) luego generar 5,000 índices aleatorios distintos en el rango' 0..N- 1', (3) elige las permutaciones del generador itertools.permutations que corresponden a estos índices. –
Sí, sé que no es el mejor. La primera vez que leí la pregunta, de alguna manera no noté esa parte 'elegida al azar'. No lo eliminaré, tal vez alguien que busque "cómo generar permutaciones de matriz en Python". lo encontrará útil. –
Es posible que desee la función itertools.permutations(). ¡Me encanta el módulo itertools!
NOTA: Nuevo en 2,6
Esto será demasiado lento, dijo que tiene 27 elementos. –
import random
perm_list = []
for i in range(5000):
temp = range(27)
random.shuffle(temp)
perm_list.append(temp)
print(perm_list)
10888869450418352160768000000 Me encanta grandes números! :)
Y
10888869450418352160768000001 es primo !!
EDIT:
#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: Este planteo nunca parar si RNG es malo!
Para comprobar también si hay duplicados como sugiere Mark, use 'perms = set()', 'perms.add (tuple (temp))', y 'while len (perms) <5000' en lugar del ciclo for. –
@Beni No seguí tu sugerencia 'tuple (temp)' al principio, pero luego entendí que era un tonto !! ¡Gracias hombre! –
# 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)
Este utiliza el código de Lehmer para la permutación como los valores de j que coinciden.
Esto puede ser muy bueno, es decir, para la compresión si necesita almacenar muchas permutaciones para usar una representación entera. Me inspiré para escribir https://gist.github.com/lukmdo/7049748 – lukmdo
Puede intentar implementar random_permutationitertools recipes. Para mayor comodidad utilizo 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 al azar para cada llamada de la función. Podemos hacer un generador que produzca estos resultados para llamadas n. Vamos a aplicar este generador y demostrar resultados al azar 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, sustituir el iterable y el número de llamadas n con los valores apropiados, por ejemplo, random_permute_generator(iterable, n=5000).
Consulte también more_itertools docs para obtener más información sobre esta herramienta.
detalles
Para los interesados, aquí está la receta real.
Desde el itertools recipes:
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))
podría valer la pena mencionar que '' 27 es 10888869450418352160768000000. –