是否有可能将n大小数组的元素均匀混洗，即任何n的概率！发生的组合是相同的，预计在O(n)时间。怎么会这样？ 我要洗牌的A元素的新数组B 是在我脑海中，当我试图做这只是选择一个随机数i从1到n的第一件事，看看是否A[i]已经回升，如果是，则重复，否则将A[i]置于B的第一个可用位置。 但是，此优惠券收集器问题的预计时间为O(n log n)。 有人可以建议一个O(n)预期的时间算法。随机排列一个数组/ n个数的元素。可能在预期的O（n）时间
谢谢。
你应该看看Fisher-Yates洗牌。
从文章：
执行得当，费雪耶茨 洗牌是公正的，让每一位 排列也同样有可能。该算法的现代版本 也相当有效，只需要 时间与正在洗牌的 项目的数量成正比，并且没有额外的 存储空间。
因此它符合您的要求。这也很容易实现。
对于各阵列位置：
选择随机位置，以结束阵列的
交换当前位置从当前位置的随机数
这应该给你为O（n），而挑战找到一个未使用的阵列位置。这假定您可以使用就地交换，并且您不必创建新阵列。
尽管大多数算法都趋向于倒序（最后到第一个），所以您可以简化随机数范围的计算。 http://www.codinghorror.com/blog/2007/12/shuffling.html，http://stackoverflow.com/questions/5383498/shuffle-rearrange-randomly-a-liststring – BMitch 2011-04-10 18:47:50
http：//en.wikipedia。 org/wiki/Fisher％E2％80％93Yates_shuffle – BMitch 2011-04-10 18:49:06
什么是BMitch描述的，叫做Knuth Shuffle。 – abc 2012-09-08 23:16:29
你想要的是random sample集合，它以相等的概率对每个元素进行采样。
在做这个的Mathematica函数中，被称为RandomSample。 http://reference.wolfram.com/mathematica/ref/RandomSample.html – Margus 2011-04-10 18:54:06
PS我试图寻找一个类似的问题，但找不到一个。如果有这样的问题，请随时链接到前面的问题，而不是回答这个问题。 – 0fnt 2011-04-10 18:41:25