洗牌算法的快速創意 - 這個工作嗎？

我正在和我的兄弟討論一個用於洗牌的快速和骯髒的算法（即每個元素都是唯一的數組）。算法描述：洗牌算法的快速創意 - 這個工作嗎？

讓卡組的卡數爲n。取一個數字x，這樣gcd(n,x)=1。現在反覆選擇卡號(x*i) mod n爲i=1高達i=n並把它放在一堆新卡（沒有從原來的甲板上，即製作一張卡的副本）。新的一堆卡將成爲我們的結果。

對我來說，似乎很清楚，只有一次執行此算法不會給出「足夠隨機」的結果（從統計測試來確定隨機性的意義上）。但是如果我們迭代地執行該算法，可能對於x的新值也滿足gcd(n,x)=1？如果這樣做足夠多的次數會給我們一個「足夠隨機」的結果，那麼我們可以預計需要多少次這樣做，作爲n的函數？

來源

2014-10-27 Sid

爲什麼要在[優秀高效算法]（http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm）已經可用時創建可疑且昂貴的算法？ – pjs 2014-10-27 14:27:47

@pjs我只對這個理論感興趣，而不是作爲一個問題的實際解決方案。 – Sid 2014-10-27 14:34:09

你會如何選擇'x'，或者你會選擇爲'x'選擇什麼？對於'gcd（n，x）'爲'1'，'x'必須是大於'n'的最小質數。所以把'n = 10，x = 11'，你會得到相同的卡組。 – 2014-10-27 14:34:58

由於模運算的奇蹟，多次執行它將會不夠。事實上，最多有n排列你所能做到這樣，而這正是當n是質1

假設你是做這個的兩倍，與x相對素n首次y相對第二次加到n。

第一次將位置p上的元素移動到p * x (mod n)。然後第二次它被移動到(p * x) * y (mod n)。這與將其移動到p * (x * y) (mod n)相同，因爲模塊化算術的關聯性。但是，如果x * y = v (mod n)那麼它將它移動到p * v (mod n) - 正如您所知，不超過n等價類。

因此，最多有n排列可能會導致一個n長度的套牌。（不，這不是一個嚴格的證明！）

編輯：，如果您使用模塊化乘冪代替我曾聲稱

，這將是優越的。然而，經過額外的考慮後，許多不重要的配置仍然會受到模塊化算術中的同樣「最多n排列」方式的影響。

來源

2014-10-27 14:35:50 Kaganar

謝謝你是對的 – Sid 2014-10-27 14:43:35

洗牌算法的快速創意 - 這個工作嗎？

回答

相關問題