随机抽样数组的唯一子集

Question

如果我有一个数组:

a = [1,2,3]

如何随机选择数组的子集,以使每个子集的元素都是唯一的？也就是说,对于a可能的子集将是:

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

我无法生成所有可能的子集,因为a的实际大小非常大,因此有许多子集.目前,我正在使用"随机游走"的想法 - 对于a的每个元素,我'翻转一个硬币'并包括它,如果硬币出现在头上 - 但我不确定这是否实际上均匀地对空间进行采样.这感觉就像它向中间施力,但是这可能只是我的脑海做模式匹配,因为会有更多的中型possiblities.

我使用正确的方法,或者我应该如何随机抽样？

(我知道这更像是一种语言不可知和'数学'的问题,但我觉得它不是Mathoverflow的真正材料 - 我只需要一个实际的答案.)

Answer 1

继续你原来的"硬币翻转"的想法.它统一地对可能性的空间进行采样.

你觉得它偏向于"中间",但这是因为"中间"的可能性数量最多.想一想:只有1种可能没有元素,只有1种含有所有元素.有N个可能性有1个元素,N个可能有(N-1)个元素.随着所选元素的数量越来越接近(N/2),可能性的数量增长得非常快.

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 是数组的长度。