python: 从二维网格中不重复抽样

Question

我需要从所有可能的数字组合中随机抽取一些样本，这些组合是从 range(n) 生成的。也就是说，我有一堆组合，比如 (0,0), (0,1), ..., (0,n), (1,0), (1,1), ..., (1,n), ..., (n,0), (n,1), (n,n)，我想从中随机选出 k 个元素。我希望能避免直接创建这个组合的完整列表。

我知道如果我只需要从一串数字中抽样，比如用 random.sample(range(n), k)，那是简单又高效的，但我现在是要从数字组合中抽样。

当然，我可以先把所有可能的组合（总共有 n * n = n^2 个）都列出来，然后再用 random.sample 来抽样。但如果 k 远小于 n^2，这样做可能就不太高效了。

我不太确定在效率方面，Python 2 和 Python 3 是否一样；我现在使用的是 Python 3。

Answer 1

没有尝试过（手边没有Python）：

random.shuffle(range(n))[:k]

看看评论吧。没睡好...

Answer 2

你说：

当然，我可以明确地构建一个包含所有可能的(n * n = n^2)元组的列表，然后调用random.sample。但如果k远小于n^2，这样做可能效率不高。

那么，如何在随机选择一个之后再构建元组呢？也就是说，如果你可以在随机选择之前构建元组，那就可以先选择，再构建。

我不太明白你的元组应该是什么样子的，但这里有一个例子，虽然我知道你的元组都是相同长度的，这个例子展示了这个原则：

而不是这样做：

>>> import random
>>> all_sequences = [range(x) for x in range(10)]
>>> all_sequences
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8]]
>>> random.sample(all_sequences, 3)
[[0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6, 7, 8]]

你可以这样做：

>>> import random
>>> selection = random.sample(range(10), 3)
>>> [range(x) for a in selection]
[[0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8]]

Answer 3

根据你选择的数量，最简单的方法可能就是记录一下你已经选过的东西（可以用一个set来实现），然后继续重新选择，直到选到一个你还没选过的。

另一种选择是用一些简单的数学方法：

numbers_in_nxn = random.sample(range(n*n), k) # Use xrange in Python 2.x
tuples_in_nxn = [divmod(x,n) for x in numbers_in_nxn]