Python：从2D网格中进行无重复抽样

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和3中的效率是否相同；我使用的是Python 3。

- max

---

元组是序列，因此您的句子“需要从数字序列而不是数字元组中获取样本”没有意义。您是否意味着您需要从元组序列中获取样本？在这种情况下，这些元组的外观不清楚。 - Lennart Regebro

你的代码(random.sample(range(n), k))适用于所有序列、元组、列表、字符串和collections.Sequence的任何子类，而且是正确的。你试过你的代码了吗？有什么问题吗？ - S.Lott

@Regebro：“元组的示例”=“从n个元组序列中选择k个元组的示例”。“序列的示例”=“从n个元素序列中选择k个元素的示例”。我要编辑问题以澄清。@S.Lott：我的意思是，我不能将序列((0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2))简单地称为一个‘range’，我无法直接应用‘sample’。 - max

Answer 1

根据您选择的数量，最简单的方法可能是仅通过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]

- Amber

---

我认为你的意思是 random.sample(range(n*n),k)，因为当我写这部分代码时，我意识到你已经把它放进去了。 - Justin Peel

+1 对我来说第二个选项似乎很完美（在将n * n替换为range(n*n)和100替换为n后）。考虑到sample被声称高效，我想不出什么情况下从集合中抽取会更好。 - max

你可以用 divmod(x,n) 替换 (x % n, x // n)。 - Kabie

如果将“range”更改为“xrange”，则在Python 2.x中也可以使用。对于聪明的答案（并且显然理解了OP想要什么），加1分。 - martineau

@Kabie，divmod(x,n)会返回(x // n, x % n)而不是(x % n, x // n)，因此它们并不完全相同，尽管我认为这在这里并不重要（因此也认为@J.F. Sebastian的评论无关紧要）。 - martineau

添加了 divmod（忘记它的存在了），并添加了关于 xrange 的注释（但由于 OP 指定了 Python 3，我为其编写了原始代码 :))。 - Amber

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]]

- Lennart Regebro

Answer 3

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

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

请看注释。没睡够...

- Howard

---

这不会给出 n x n 的元组，因为它永远不会给出 (1,1) 这样的结果。 - Amber

但是，“不重复”是什么意思呢？啊，现在我明白了。k个长度为n的不同元组。 - Howard