Muestreo de permutaciones de [1, 2, 3, ..., N] para grande N

Question

Tengo que resolver the Travelling Salesman Problem usando un genetic algorithm que tendré que escribir para tarea.

El problema consiste en 52 ciudades. Por lo tanto, el espacio de búsqueda es 52!. Necesito muestrear aleatoriamente (digamos) 1000 permutaciones de range(1, 53) como individuos para la población inicial de mi algoritmo genético.

Con el fin de hacer esto, he intentado:

>>> random.sample(itertools.permutations(range(1, 53)), 1000) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/usr/lib/python2.6/random.py", line 314, in sample 
    n = len(population) 
TypeError: object of type 'itertools.permutations' has no len() 

así que traté

>>> random.sample(list(itertools.permutations(range(1, 53))), 1000) 

Sin embargo, dado que 52! es muy grande, la operación list es el gasto excesivo con el espacio de memoria y de intercambio en mi computadora. No puedo elegir las primeras 1000 permutaciones generadas por itertools.permutations porque es muy determinista y eso sesgaría mi algoritmo genético.

¿Hay una mejor manera de lograr este muestreo?

Answer 1

No necesita permutar en absoluto. Llame al random.sample(range(52), 52) 1000 veces.

P.S .: Realmente debería utilizar la indexación basada en cero (range(52) en comparación con range(1, 53)) en todo su trabajo. Las cosas generalmente funcionan mejor de esa manera.