雖然不是最佳做法,整理一年前想到的做法,留個記錄
原本的構想已經拆成二個 class
- 產生 index 的排列組合順序,例: {0,0,0} {0,1,0} {1,0,0} {1,1,0} {2,0,0} {2,1,0}
- 透過 index 排列組合順序,來得到所需的結果,例: 對 {1,2,3} 排列的結果為 {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
最後把他合到一個 class 中, GitHub連結:https://github.com/ragnakuei/Permutation
在長度為三的情況下,要進行排列組合
假設要排列的資料為 {1,2,3} (parameter name:source)
預期會得到的結果是 {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1} (property name:Result)
構想:
先產生一組 List<int>{0,0,0} 的資料 (field name: _indexPermutation )
取值的方式:
cloneIndex | cloneSource | tmpResult | |
1 | {0,0,0} | {1,2,3} | {} |
2 | {0,0} | {2,3} | {1} |
3 | {0} | {3} | {1,2} |
4 | {} | {} | {1,2,3} |
註:
cloneIndex : 從 _indexPermutation 複製出來的,要用複製的原因是還要保留原本的資料
cloneSource : 從 source 複製出來的,要用複製的原因同上
tmpResult : 單次處理完畢後,就會將這個結果加到 Result 中
上面的例子其實還看不出實際的感覺,接下來繼續:
cloneIndex | cloneSource | tmpResult | |
1 | {2,1,0} | {1,2,3} | {} |
2 | {1,0} | {1,2} | {3} |
3 | {0} | {1} | {3,2} |
4 | {} | {} | {3,2,1} |
第1步: cloneIndex[0] 的值是 2,就會取出 cloneSource[2] 的值=3,來放進 tmpResult 中
取出後,就刪掉 cloneIndex[0] 與 cloneSource[2] 的資料,來避免取出重複的值
第2步: cloneIndex[0] 的值是 1,就會取出 cloneSource[1] 的值=2,來放進 tmpResult 中
之後類推~!!
有了這個取值規則後,那麼接下來,只要讓 cloneIndex 產生 {0,0,0} {0,1,0} {1,0,0} {1,1,0} {2,0,0} {2,1,0} 這樣的結果
就可以順利取出所有的排組合
我的做法是透過 _indexPermutation & 進位 & Reverse() 來達成:
先從{0,0,0}開始
對 index=1的位置+1, 產生 {0,1,0}
對 index=1的位置+1,產生 {0,2,0},進位,變成 {0,0,1}
對 index=1的位置+1, 產生 {0,1,1}
對 index=1的位置+1,產生 {0,2,1},進位,變成 {0,0,2}
對 index=1的位置+1, 產生 {0,1,2}
每次 _indexPermutation +1 後,就 Reverse() 順序來產生 cloneIndex
進位的判斷是,只要該 value 的值,大於該 value 所在的 index 值,就執行(往右)進位的動作
進位到最大的值 {0,1,2} 時,就讓 _endFlag = true,代表已經計算完畢
這些部份組合起來,就可以達到任意長度做排列組合了~!!