说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.
请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.
如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.
从Steven Skiena的算法设计手册中得到了这个问题.
需要选择k(给定值)数以从具有n个数的给定集合S形成子集S',使得每个数的选择概率相等(k/n).n是未知的(我正考虑将S作为链接列表).另外,我们只能通过集合S.