循環遍歷所有組合

我試圖用Java編寫多人遊戲。循環遍歷所有組合

我需要創建一個所有組合的列表並將它們存儲在一個數組中。

如果2名玩家登錄的遊戲開始，該組合是： P1，P2和P2，P1（位置是重要的）

而如果3名玩家登錄到遊戲中，組合是： p1，p2，p3; p1，p3，p2; p2，p1，p3; p2，p3，p1; P3，P1，P2和P3，P2，P1

事實上，我需要的冗餘陣列：如果3名玩家登錄，我需要提前的3每個可能對 p1的組合的組合和， p2，p3; p1，p3，p2; p2，p1，p3; p2，p3，p1; P3，P1，P2和P3，P2，P1 和 P1，P2和P2，P1 和 P1，P3和P3，P1 和 P2，P3和P3，P2 ）

許多玩家（編輯：最多8名玩家）可能會同時登錄遊戲的同一輪。（編輯：有多達32個組，但這並不重要，因爲組是獨立的）

是否有一種快速，簡短和簡單的方法來爲n個玩家創建這個組合數組？

遞歸解決方案是可預見和可接受的。

非常感謝

P.S.

我持續的想法是將該組分成2個，一個選定的對和其他玩家。使用2個FOR循環選擇sekected對，其餘的選擇第三個。如果有2名球員，則不會「休息」，如果有3名球員，則2名球員將選擇球員的位置，其餘球員將獲得剩餘球員。再次感謝

來源

2012-01-15 elarrow

嘗試1：http：// stackoverflow。com/questions/4555565/generate-all-ofsets-of-size-k-from-a-set – alf 2012-01-15 17:10:24

嘗試2：http://www.cut-the-knot.org/do_you_know/AllPerm.shtml – alf 2012-01-15 17:10:59

解決方案可能是*短*和*簡單*，但絕對沒有辦法枚舉到256！組合可能*快*。 – dasblinkenlight 2012-01-15 17:11:00

你知道每個數組中的條目數對於包含所有播放器的數組，它是256！這是數組中第一個條目的可能性，255爲下一個，等等，256！是一個足夠大的數字，以至於我的計算器無法處理它，即使是170個玩家，數組的大小也是1.3e241，即使在64位計算機上，有1.8e19個可尋址的字節，這基本上意味着你需要重新考慮你的方法

來源

2012-01-15 17:16:35 Mike

大小爲n的排列數是n！，它以指數級增長。例如，20個元素的所有排列的數目是2432902008176640000（〜2.43290201×10^18），相當大的數目。

就像你猜對了，還有用於生成所有排列一個recursive algorithm，但它是在時間和空間上面列出的理由相當ineffecient。

但是，如果您的任務正在生成隨機排列，則確實存在有效的算法：Fisher–Yates shuffle。它需要O（n）時間（假設你可以在O（1）中產生一個隨機整數），並且O（1）是額外的存儲器。

來源

2012-01-15 17:18:00

循環遍歷所有組合

回答

相關問題