Перестановки выборки [1,2,3,,N] для больших N

Мне нужно решить задачу коммивояжера с помощью генетический алгоритм, который мне придется написать в качестве домашнего задания.

Задача состоит из 52 городов. Таким образом, область поиска 52!. Мне нужно случайным образом отобрать (скажем) 1000 перестановок range(1, 53) как особей для начальной популяции моего генетического алгоритма.

Чтобы сделать это, я попытался:

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

Так что я попытался

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

Однако, учитывая, что 52! ОЧЕНЬ большой, операция list максимально использует память и пространство подкачки на моем компьютере. Я не могу просто выбрать первую 1000 перестановок, сгенерированных itertools.permutations, потому что это очень детерминировано, и это исказило бы мой генетический алгоритм.

Есть ли лучший способ добиться этой выборки?


python large-data sample-data genetic-algorithm
person inspectorG4dget    schedule 28.01.2012    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Вам вообще не нужно переставлять. Позвоните random.sample(range(52), 52) 1000 раз.

P.S.: Вы действительно должны использовать индексацию с отсчетом от нуля (range(52) вместо range(1, 53)) во всей своей работе. Обычно так дело обстоит лучше.

person Marcelo Cantos    schedule 28.01.2012
comment
Я полностью согласен с вашей нулевой индексацией, но индексы здесь представляют собой идентификаторы городов, и мой проф решил, что он хочет начать с 1... Поэтому я пытаюсь оставаться верным его соглашению. - person inspectorG4dget; 29.01.2012
comment
По моему опыту, вы должны просто делать это по-своему и преобразовывать его в дерьмовые соглашения вашего профессора в ваших выходных утверждениях. - person machine yearning; 29.01.2012
comment
Подождите, для случайной перестановки это не должно быть p = range(10); random.shuffle(p)? random.sample будет дублировать некоторые значения и пропускать другие. Но, возможно, вы говорите, что на самом деле это не обязательно должны быть перестановки... - person senderle; 29.01.2012
comment
@senderle random.sample работает без замены, если он действительно производит перестановку. Когда размер выборки совпадает с размером совокупности, он эквивалентен random.shuffle() для совокупности (за исключением того, что перемешивание с перетасовкой на месте и выборкой оставит исходный текст без изменений). - person Raymond Hettinger; 29.01.2012