7

如果我有一个数组：

a = [1,2,3]

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

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

我无法生成所有可能的子集，因为 a 的实际大小非常大，所以有很多很多子集。目前，我正在使用“随机游走”的想法——对于 a 的每个元素，我会“抛硬币”并在硬币正面朝上时将其包括在内——但我不确定这是否真的均匀地采样了空间。感觉它偏向中间，但这可能只是我在做模式匹配的想法，因为会有更多中等大小的可能性。

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

（我知道这更像是一个与语言无关的“数学”问题，但我觉得这不是真正的 Mathoverflow 材料——我只需要一个实用的答案。）

4

5 回答 5

5

继续你原来的“抛硬币”的想法。它均匀地对可能性空间进行采样。

你觉得它偏向“中间”，但那是因为“中间”的可能性数量最多。想一想：没有元素的可能性只有 1 种，所有元素的可能性只有 1 种。有 1 个元素有 N 种可能性，有 (N-1) 个元素有 N 种可能性。随着所选元素的数量越来越接近 (N/2)，可能性的数量增长得非常快。

于 2012-01-19T21:52:53.150 回答
1

您可以生成随机数，将它们转换为二进制并从原始数组中选择位为 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 是数组的长度。

于 2012-01-19T17:43:09.263 回答
0

I think the coin flipping is fine. 

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

An array with 10 elements has 2**10 possible combinations (including [ ] and all 10 elements) which is nothing more then 10 times (1 or 0). It does output more arrays of four, five and six elements, because there are a lot more of those in the powerset.

于 2012-01-19T21:04:10.407 回答
0

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

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，然后随机选择其中一个整数（实际上是均匀随机的）。然后它将整数解码回array使用位掩码的特定子集（1 = 元素在子集中，0 = 不在）。

通过这种方式，您可以在阵列的功率集上均匀分布。

于 2012-01-20T12:40:56.797 回答
0 
a.select {|element| rand(2) == 0 }

对于每个元素，都会翻转一枚硬币。如果正面（== 0），则它被选中。

于 2012-01-19T19:02:59.083 回答