複雜的Java排列生成問題

我試圖找出產生的序列是數字固定編號和每一個數字都有不同的字母所有可能的排列的最好方式。複雜的Java排列生成問題

我有許多整數數組，並且每一個都可以具有不同的長度併產生置換當只有數組的值可以佔據在最終結果中的排名。

一個具體實例是所謂的條件與下列數據int數組：

conditions1 = {1,2,3,4} 
conditions2 = {1,2,3} 
conditions3 = {1,2,3} 
conditions4 = {1,2} 
conditions5 = {1,2}

和我要創建的所有可能的排列的5列表 - 這種情況下144（4x3x3x2x2）。第1欄只能使用值從條件1和conditions2列2等

輸出爲：

1,1,1,1,1 
1,1,1,1,2 
1,1,1,2,1 
1,1,1,2,2 
1,1,2,1,1 
. 
. 
through to 
4,3,3,2,2

它已經太久太久，因爲，因爲我已經做任何的這些東西，大部分我發現的信息涉及所有字段使用相同字母表的排列。我可以使用它，然後在刪除所有具有無效值但列表效率低下的列的排列後運行測試。

我想在這裏感謝所有幫助。

來源

2011-04-02 Zoran

寫一些代碼，你將面臨的問題，然後提出問題 - 是不是很容易呀？ – Nishan 2011-04-02 13:48:15

我確實寫了一些代碼。問題是當每個條件的長度相同時，代碼運行良好。但是當我嘗試不同的長度時，它會崩潰。 – Zoran 2011-04-02 15:52:36

然後顯示代碼，我們可以幫助你改變它做正確的事情。（順便說一下，*排列*不正確的話（因爲你不改變順序） - *變化*會更適合。） – 2011-04-02 16:34:14

看起來可能不需要遞歸。

Iterator<int[]> permutations(final int[]... conditions) { 
    int productLengths = 1; 
    for (int[] arr : conditions) { productLengths *= arr.length; } 
    final int nPermutations = productLengths; 
    return new Iterator<int[]>() { 
    int index = 0; 
    public boolean hasNext() { return index < nPermutations; } 
    public int[] next() { 
     if (index == nPermutations) { throw new NoSuchElementException(); } 
     int[] out = new int[conditions.length]; 
     for (int i = out.length, x = index; --i >= 0;) { 
     int[] arr = conditions[i]; 
     out[i] = arr[x % arr.length]; 
     x /= arr.length; 
     } 
     ++index; 
     return out; 
    } 
    public void remove() { throw new UnsupportedOperationException(); } 
    }; 
}

在Iterable<int[]>結束語將使其更容易與for (... : ...)循環使用。你可以通過取消迭代器接口來取消數組分配，只需將數組作爲參數來填充即可。

來源

2011-04-02 15:55:42

感謝麥克。好多了。這很好。只是一個簡單的問題，你介意解釋out [i] = arr [x％arr.length]的原理嗎？和x/= arr.length;因爲它們幾乎是它的膽量。 – Zoran 2011-04-02 17:13:57

@Zoran，即使它不是一個遞歸算法，你可以遞歸地思考它。如果我有從陣列的其餘部分的第一陣列中n個元素，且o * P * Q置換，然後我可以通過挑選使用餘量（'％'）的n的一個，然後將得到的減少的問題索引與其餘數組一起使用。 – 2011-04-02 17:20:25

複雜的Java排列生成問題

回答

相關問題