是否有可能將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