改換一堆鑰匙

這個問題主要涉及一個洗牌的着名採訪問題。我徘徊於SO並發現了類似的問題，但答案大多不符合標準，或者被忽略。改換一堆鑰匙

給出的問題是建立一個函數來洗牌。

我的解決方案：這是可能的，如果我把所有的卡以任何順序（如排序或未排序 - 順序無關緊要）鏈接列表。我生成一個隨機數，將其mod改爲當前的卡片總數，並從鏈接列表中刪除該索引以將卡片存儲在我的shuffledArray中。

我認爲這個解決方案非常好，它有以下運行時間： O（n）用於以任意順序構建鏈表。 O（n）用於將其從鏈接列表中刪除。 O（1）每次產生一個隨機數。

所以或多或少，我們有這個算法的O（n）的下界。

我擔心的是空間。目前採用的空間如下： 1）O（n）爲鏈表 2）O（n）爲shuffledArray。

再次是O（n）的下界。

這可以做到位嗎？我的意思是沒有使用這個額外的空間。它可以在小於O（n）的時間內完成嗎？

2012-06-02 dharam

到位仍然是O（n），對不對？ – Junuxx

標準答案：[Fisher-Yates]（http://en.wikipedia.org/wiki/Fisher-Yates_shuffle）。 – Gumbo

是的，這將是，但會想到在這種情況下，n越來越大的訂單1,000,000 n和2n有所作爲 – dharam

Fisher-Yates shuffle就地工作，並且確實產生n-1個隨機數。

2012-06-02 19:04:05 kilotaras

我想了解這個算法，但它的種類超出了我的想象。 – dharam

它和Andrew寫的一樣，只是從另一端開始。你增加大小，而不是減少。 – kilotaras

void shuffle(vector<T> v) 
{ 
    int n = v.size(); 
    for (int i = 0; i < n; i++) 
     swap(v[i], v[i+rand(n-i)]); 
};

證明通過感應：

2012-06-02 19:04:03

哦！你在我做之前回答。：P – spicavigo

-1

如何迭代卡片。在每一步中，您將生成一個介於1和52之間的隨機數，並將當前卡與該隨機數中的卡交換？

您對此有何看法？

2012-06-02 19:08:52 spicavigo

我可能最終交換同一組卡片;） – dharam

這會使用比必要更多的熵。你應該只需要N！隨機狀態匹配N！均勻分佈的候選置換。 –

是的。我認爲安德魯的解決方案將在這種情況下工作。或者這個Fisher-Yates建議的事情由kiloataras – spicavigo

回答