我有这个问题
您将获得一组n个数字.您必须从S中选取k个数的子集S',使得在S'中出现的S的每个元素的概率相等(即,每个元素以概率k/n选择).你可以只对这些数字进行一次传球.如果n未知怎么办？
我甚至有一个解决方案:http://www.algorithm.cs.sunysb.edu/algowiki/index.php/TADM2E_2.43
仍然:我根本不理解问题文本.
我给了一组n个数字.精细.我需要选择一个k数的子集(可能有2 ^ n个子集),这样S中每个元素出现的概率都是相等的......对我来说,明显的答案就是抓住空S'集合:S中的每个元素都有0个概率在S'中.
如果这是不可接受的(并且应该已经说明了),我想我应该在S中计算最重复的元素(出现T次)并使其他所有元素在S'中具有正好的T实例(它应该仍然是子集,如果元素包含在S)中.
我真的不了解优先级队列解决方案,也不了解k/n概率.有人可以帮我解决这个问题吗？