作者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