作者chrisdar (克里斯)
看板Prob_Solve
標題[問題] 關於重複組合的演算法問題
時間Tue Dec 9 17:58:04 2008
※ [本文轉錄自 C_and_CPP 看板]
作者: chrisdar (克里斯) 看板: C_and_CPP
標題: [問題] 關於重複組合的演算法問題
時間: Tue Dec 9 14:01:13 2008
關於重複組合的演算法問題
我想了一個演算法模仿next_permutation(疊代型)，
我稱做 next_combination。
用法類似這樣
string ss("0011223344");
do{
cout << ss.substr(0,3) << endl;
}while (next_combination(ss.begin(),ss.begin()+3,ss.end()));
舉例0011223344要取3個作組合
００１１２２３３４４
├─┤ → 1必須要向後找到一個大於他的與之交換
００２１１２３３４４
├───┤
００３１１２２３４４
├─────┤ ↗００４１１２２３３４ 由於４找不到比他大的，則往
００４１１２２３３４ ／ ├┼┼┤ →前推移一位， 04 跟 11 交換
├┼┼┤ → ０１１０４２２３３４
０１１０２２３３４４ ╲ ├────┤→交換後需要rotate旋轉1次
├─┤ ↘０１１０２２３３４４
０１２０１２３３４４
├───┤
０１３０１２２３４４
├─────┤ ↗０１４０１２２３３４ 由於４找不到比他大的，則往
０１４０１２２３３４ ╱ ├┼──┼┤ →前推移一位， 14 跟 22 交換
├┼──┼┤ → ０２２０１１４３３４
０２２０１１３３４４ ╲ ├──┤→交換後需要rotate旋轉1次
├───┤ ↘０２２０１１３３４４
０２３０１１２３４４
├─────┤ ↗０２４０１１２３３４ 由於４找不到比他大的，則往
０２４０１１２３３４ ╱ ├┼────┼┤ →前推移一位， 24 跟 33 交換
├┼────┼┤ → ０３３０１１２２４４
０３３０１１２２４４ ╲ ├┤→交換後需要rotate旋轉1次
├─────┤ ↘０３３０１１２２４４
０３４０１１２２３４
├┼──────┼┤→原本要交換兩個因為到底了就只換一個
０４４０１１２２３３
├┼┼──┼┼┤ ┐ ↗０４４０１１２２３３ 由於４找不到比他大的，則往
１１２００２３３４４ ↓╱ ├┼┼─┼┼┤ →前推移1+1位，044跟 112交換
├───┤ └ １１２００４４２３３
１１３００２２３４４ ╲ ├───┤→交換後需要rotate旋轉2次
├─────┤ ↘１１２００２３３４４
１１４００２２３３４
├┼──┼┤ →同之前的算法
１２２００１３３４４
├───┤
１２３００１２３４４
├─────┤
１２４００１２３３４
├┼────┼┤ →同之前的算法
１３３００１２２４４
├─────┤
１３４００１２２３４
├┼──────┼┤→原本要交換兩個因為到底了就只換一個
１４４００１２２３３
├┼┼───┼┼┤ →同之前的算法
２２３００１１３４４
├─────┤
２２４００１１３３４
├┼────┼┤
２３３００１１２４４
├─────┤
２３４００１１２３４
├┼──────┼┤→原本要交換兩個因為到底了就只換一個
２４４００１１２３３
├┼┼─────┼┼┤→原本要交換三個因為到底了就只換兩個
３３４００１１２２４
├┼──────┼┤→原本要交換兩個因為到底了就只換一個
３４４００１１２２３
├────────┤ →完全找不到比 344還大的就旋轉 3次。 並 return false
００１１２２３３４４
我想問一下：
0.這是正確得演算法嗎？
1.這個演算法的時間複雜度是O(n)嗎？
2.有更有效率的做法嗎？
3.這個演算法好不好實作？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.23.35.94
1F：推 gba356:我比較有問題的是 04 和 11 交換，要怎麼判斷選擇 11 ？ 12/09 17:14
2F：→ gba356:又 1, 1 不一定相連呀，所以可能每次要 sort 一次 12/09 17:15
3F：→ gba356:rotate 的部分應該是 sort 吧，用 sort 才能保證找到最小字 12/09 17:15
4F：→ gba356:點序 12/09 17:15
5F：→ gba356:例如 ss("0014433221") 呢？ 12/09 17:17
6F：→ chrisdar:next_combination跟next_permutation一樣 使用前要先排序 12/09 17:30
００４１１２２３３４
└─────── →一直找不到比4大的
００４１１２２３３４
└─┘ →找到比0大的
００４１１２２３３４
├─┤ →交換0跟1
０１４０１２２３３４
├─┤ →交換4跟1
０１１０４２２３３４
├────┤ →交換後需要rotate旋轉1次
０１１０２２３３４４
１３４００１２２３４
└─────── →一直找不到比4大的
１３４００１２２３４
└───────┘ →找到比3大的
１３４００１２２３４
├───────┤ →交換3跟4
１４４００１２２３３
├─────── →這邊因為沒東西可以換了就不用換了
１４４００１２２３３ 也不用旋轉了
7F：推 gba356:next_permutation() 不用吧..這是他方便之所在.. 12/09 17:36
0014433221 他是某一個 next_permutation 的解 (解1可以疊代出解2)
不是我的 next_combination 的解 (我認為的)
不過可以加上 sort 來轉換 這個倒是可以加進去
說明可以這樣寫明 如果輸入不屬於解空間之一則會轉換到下一個解
0014433221 -> 0021123344
※ 編輯: chrisdar 來自: 163.23.35.94 (12/09 17:57)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.23.35.94
8F：推 hannibal0416:推一下，感覺打的很辛苦 08/18 13:31