作者jimian (ian)
看板EE_DSnP
标题[问题] 关於permutation与recursion
时间Wed Oct 29 22:51:02 2008
以下是我所撰写的permutation函式，功能是对一个int阵列中的数字做排列组合:
void permutation(int *v, const int start, const int n){
if(start==n-1){
possibility++;
print(v,n);//印出某排列
}
else
{
for (int j = start; j < n; j++) {
int tmp=v[start];
v[start]=v[j];
v[j]=tmp;
permutation(v,start+1,n);
v[j]=v[start];
v[start]=tmp;
}
}
}
不过这个函式在使用上会出现一个状况：如果我要它找3,2,2的所有排列，就会出现以下
结果：
===The permutations of {2,2,3}are===
2 2 3
2 3 2
2 2 3
2 3 2
3 2 2
3 2 2
===Total permutations:6===
出现了好几个重复的可能，也就是如果要排列的数字有重复的话会有问题
(不过如果是皆不同的数字就没关系)
我曾经用过一些方法企图排除重复的状况(包含老师今天上课提到的)
不过反而连该出现的可能都不见了
请问是不是我用的这个方法的问题呢?
程式还要做些什麽修改呢?
请强者指点一下，谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.133.129.229
1F：推 ric2k1:检查一下, 相同的就不用 swap 了... 10/29 22:57
2F：→ ric2k1:找不出来可试用 cout or debugger 来 debug... 10/29 22:57
3F：→ jimian:有试过当v[start]==v[j]时跳过swap程序，不过发现会少掉 10/29 23:39
4F：→ jimian:一些可能 10/29 23:39
5F：→ jimian:当时我是把v[start]=v[j]; v[j]=tmp; permutation(...) 10/29 23:41
6F：→ jimian:这一大段用if(v[start]!=v[j]){...}包起来，以让程式碰到 10/29 23:43
7F：→ jimian:重复的就不用swap了，结果发现会少掉一些可能... 10/29 23:43
※ 编辑: jimian 来自: 220.133.129.231 (10/29 23:43)
8F：推 ric2k1:先 swap 还是先 permute 啊... 想一下 10/30 00:01