大N的[1,2,3，...，N]的抽样排列 [英] Sampling Permutations of [1,2,3,...,N] for large N

问题描述

我必须使用

I have to solve the Travelling Salesman Problem using a genetic algorithm that I will have to write for homework.

问题包括52个城市.因此，搜索空间为 52！.我需要随机抽样(比如说)1000个排列范围的 range(1，53)作为个体，作为我的遗传算法的初始种群.

The problem consists of 52 cities. Therefore, the search space is 52!. I need to randomly sample (say) 1000 permutations of range(1, 53) as individuals for the initial population of my genetic algorithm.

为此，我尝试:

>>> 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个排列，因为它具有确定性，并且会影响我的遗传算法.

However, given that 52! is VERY large, the list operation is maxing out the memory and swap space on my computer. I can't just pick the first 1000 permutations generated by itertools.permutations because it's very deterministic and that would bias my genetic algorithm.

有没有更好的方法来实现这种采样?

Is there a better way to achieve this sampling?

推荐答案

您根本不需要进行置换.调用 random.sample(range(52)，52) 1000次.

You don't need to permute at all. Call random.sample(range(52), 52) 1000 times.

P.S .:在所有工作中，您实际上应该使用从零开始的索引( range(52)，而不是 range(1，53)).这样一来，事情通常会更好.

P.S.: You really should use zero-based indexing (range(52) as opposed to range(1, 53)) in all your work. Things generally work out better that way.

这篇关于大N的[1,2,3，...，N]的抽样排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！