在不将可迭代 (itertools.combinations) 转换为列表的情况下改组组合

Question

下面的简单代码给出了长度为 3 的 200 个元素的可能组合。

from itertools import combinations
comb = combinations( range(200), 3 )

我想以随机顺序获取组合，以便选择前 N 个组合。但是，如果我将 comb 转换为列表并将其按如下方式打乱，我可能会出现内存错误，因为列表可能包含太多元素：

comb = list(comb) # This might be huge and give a memory error 
random.shuffle(comb)
N = 10
comb = comb[:10] # get only the first N random combinations

有没有其他方法可以得到N个随机组合？（即不按 itertools.combinations 生成的顺序）。

Answer 1

有 C(200, 3) = 1313400 种可能的组合。正如您还提到的，由于 combinatorial explosion，这个数字很容易失控。例如，如果您选择 4 个而不是 3 个元素，则组合数将增加大约 50 倍 (64684950)。您可以随机构建可能的组合，而不是从这些组合中随机选择。

要构建这些组合，您可以使用随机库中的 random.sample。 random.sample(range(200), 3) 将随机生成这 1313400 种组合中的一种。如果您再次调用它，它将生成另一个组合。

有两个问题：

顺序在 random.sample 中很重要（[1, 2, 3] 不同于 [1, 3, 2]）。在组合中，它不是。要解决这个问题，您可以使用 sorted().
random.sample 将独立生成接下来的 3 个数字。因此，在不同迭代中生成的组合可能是相同的。虽然对于此示例 (≈0.0000343) 来说不太可能，但您可以使用集合来存储组合，以便只存储唯一的组合。

以下将生成 10 种不同的组合：

import random
combs = set()
N = 10
while len(combs) < N:
    combs.add(tuple(sorted(random.sample(range(200), 3))))

在不将可迭代 (itertools.combinations) 转换为列表的情况下改组组合

Shuffling combinations without converting iterable (itertools.combinations) to list

python

combinations

shuffle

itertools