对于大的N，如何对[1,2,3,...,N]进行排列组合抽样

Question

我需要用遗传算法解决旅行商问题，这是我的作业。该问题包含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操作会占用计算机的内存和交换空间。我不能只选择由itertools.permutations生成的前1000个排列，因为这是非常确定性的，会对我的遗传算法产生偏差。

有更好的方法来实现这种抽样吗？

- inspectorG4dget

Answer 1

您无需进行任何排列。调用random.sample(range(52), 52)1000次即可。

P.S.：在所有工作中，您确实应该使用从零开始的索引（range(52)而不是range(1,53)）。这样事情通常会更好。

- Marcelo Cantos

---

我完全同意你的零基索引，但这里的索引代表城市ID，我的教授决定从1开始...所以我试图遵循他的惯例。 - inspectorG4dget

我的经验是，你应该按照自己的方式做，并在输出语句中将其转换为教授的糟糕规范。 - machine yearning

等等，对于一个随机的排列，这应该是 p = range(10); random.shuffle(p) 吧？random.sample 会重复一些值并省略其他值。但也许你是在说这些实际上不必是排列... - senderle

random.sample函数在抽样时不会重复，因此它确实会产生一种排列方式。当抽样大小与总体大小相同时，它等同于对总体进行random.shuffle()操作（除了shuffle方法是原地进行排序的，而sample则不会改变原始数据）。 - Raymond Hettinger