随机采样数组的唯一子集 [英] Randomly sampling unique subsets of an array

问题描述

如果我有一个数组:

a = [1,2,3]

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

How do I randomly select subsets of the array, such that the elements of each subset are unique? That is, for a the possible subsets would be:

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

我无法生成所有可能的子集，因为a的实际大小非常大，因此有很多子集.目前，我正在使用随机漫步"的想法-对于a的每个元素，我都会翻转硬币"，并在硬币正面朝上时将其包括在内-但我不确定这是否实际上对空间进行了均匀采样. 感觉，就像它偏向中间一样，但这可能只是我的想法，进行模式匹配，因为会有更多中等大小的可能性.

I can't generate all of the possible subsets as the real size of a is very big so there are many, many subsets. At the moment, I am using a 'random walk' idea - for each element of a, I 'flip a coin' and include it if the coin comes up heads - but I am not sure if this actually uniformly samples the space. It feels like it biases towards the middle, but this might just be my mind doing pattern-matching, as there will be more middle sized possiblities.

我是使用正确的方法还是应该随机抽样?

Am I using the right approach, or how should I be randomly sampling?

(我知道这更多是与语言无关的数学"问题，但我认为这并不是Math Mathflow的实质内容，我只需要一个实际的答案即可.)

(I am aware that this is more of a language agnostic and 'mathsy' question, but I felt it wasn't really Mathoverflow material - I just need a practical answer.)

推荐答案

只需继续执行您最初的掷硬币"想法.它对可能性空间进行统一采样.

Just go ahead with your original "coin flipping" idea. It uniformly samples the space of possibilities.

在您看来，您喜欢偏向中级"，但这是因为在中级"中可能性最大.想一想:只有一种可能性，没有任何要素，只有一种，具有所有要素. 1个元素有N个可能性，(N-1)个元素有N个可能性.随着所选元素的数量越来越接近(N/2)，可能性的数量会迅速增加.

It feels to you like it's biased towards the "middle", but that's because the number of possibilities is largest in the "middle". Think about it: there is only 1 possibility with no elements, and only 1 with all elements. There are N possibilities with 1 element, and N possibilities with (N-1) elements. As the number of elements chosen gets closer to (N/2), the number of possibilities grows very quickly.

这篇关于随机采样数组的唯一子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！