排列-做法1

  • 199
  • 0
  • C#
  • 2017-02-04

雖然不是最佳做法,整理一年前想到的做法,留個記錄

原本的構想已經拆成二個 class

  1. 產生 index 的排列組合順序,例: {0,0,0} {0,1,0} {1,0,0} {1,1,0} {2,0,0} {2,1,0}
  2. 透過 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,代表已經計算完畢

這些部份組合起來,就可以達到任意長度做排列組合了~!!