随机抽取一个数组的唯一子集

Question

如果我有一个数组：

a = [1,2,3]

如何随机选择数组的子集，使得每个子集的元素都是唯一的？也就是说，对于a而言，可能的子集包括：

[]
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]

由于a的实际大小非常大，因此我无法生成所有可能的子集，因为有许多，许多子集。目前，我正在使用“随机游走”的想法-对于a的每个元素，我会'掷一枚硬币'并在硬币正面朝上时包含它-但我不确定这是否真正均匀地抽样了空间。感觉偏向中间，但这可能只是我大脑进行模式匹配，因为会有更多中等大小的可能性。

我是否使用了正确的方法，或者应该如何进行随机抽样？

（我知道这更像是一个与语言无关和“mathsy”问题，但我觉得这并不是数学堆栈材料-我只需要一个实用的答案。）

- meagerf

---

我假设 a 不会是一个整数数组？ - Michael Kohl

不好意思，我实际的例子中是一个字符串数组。 - Stephen

Answer 1

请继续使用您最初的"抛硬币"想法。它能够均匀地对可能性空间进行抽样。

您觉得它偏向于"中间"，但这是因为"中间"的可能性最多。请思考一下：没有元素的情况只有1种可能，所有元素都在的情况也只有1种可能。选择1个元素时有N种可能，选择(N-1)个元素时也有N种可能。当所选元素数量接近(N/2)时，可能性的数量会迅速增加。

- Alex D

---

a.select {|element| rand(2) == 0 } - Martin Velez

a.select {|| rand(2).zero? } 可以翻译为“从数组a中选择满足随机条件的元素”。其中，代码块 {|| rand(2).zero? } 表示对于 a 中的每个元素，以 50% 的概率保留该元素或者将其删除。最终返回的是一个新的数组，其中包含了随机选择的元素。;-) - Michael Kohl

Answer 2

你可以生成随机数，将它们转换为二进制，并选择原始数组中二进制位为1的元素。这是一个针对Array类的猴子补丁实现：

class Array
  def random_subset(n=1)
    raise ArgumentError, "negative argument" if n < 0
    (1..n).map do
      r = rand(2**self.size)
      self.select.with_index { |el, i| r[i] == 1 }
    end
  end
end

使用方法：

a.random_subset(3) 
#=> [[3, 6, 9], [4, 5, 7, 8, 10], [1, 2, 3, 4, 6, 9]]

一般来说，这个算法表现还不错，时间复杂度为O(n*m)，其中n是你想要的子集数量，m是数组的长度。

- Michael Kohl

Answer 3

a.select {|element| rand(2) == 0 }

针对每个元素，都会抛一枚硬币。如果正面朝上（等于0），则选中该元素。

- Martin Velez

---

sample(rand * a.size) 会生成长度在0到a.size - 1之间的子集。如果你想要排除空集，并包含超集，则使用 sample(rand(a.size) + 1)。 - Wayne Conrad

我使用了 rand(a.size + 1)，它似乎可以生成空子集 [] 和子集 a 本身。因此，它可以生成 a 的所有可能子集。 - Martin Velez

请注意，Array#sample 在 Ruby 1.9 及以上版本中可用。 - zetetic

这不是 a 的幂集上的均匀分布，因为它首先选择一个长度，然后再从该长度中随机取样。在 a 的幂集中，长度为 2 的集合比长度为 a.length 的集合明显要多得多！ - Alberto Santini

@AlbertSantini 我同意你的观点。我改变了我的答案。 - Martin Velez

Answer 4

我认为硬币翻转是没问题的。

ar = ('a'..'j').to_a
p ar.select{ rand(2) == 0 }

一个包含10个元素的数组有2**10种可能的组合（包括[ ]和所有10个元素），这不过是10次（1或0）而已。它会输出更多的四、五和六个元素的数组，因为在幂集中有更多这样的元素。

- steenslag

Answer 5

选择幂集中的随机元素的方法如下：

my_array = ('a'..'z').to_a
power_set_size = 2 ** my_array.length
random_subset = rand(power_set_size)
subset = []
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element|
  subset << my_array[corresponding_element] if bit == "1"
end

为了方便起见，这里使用字符串函数而不是实际的“位”和位运算。您可以通过使用实际的位来将其转换为更快（我猜）的算法。

它所做的是将array的幂集编码为介于0和2 ** array.length之间的整数，然后随机选择其中一个整数（确实是均匀随机）。然后，它使用位掩码（1 =元素在子集中，0 =不在）将整数解码回array的特定子集。

通过这种方式，您可以获得数组幂集的均匀分布。

- Alberto Santini

---

我刚注意到Michael Kohl发布了类似的解决方案，可能会更好。它使用真正的位运算，并且还可以让你请求多个子集。 - Alberto Santini