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