作者boombastick (快樂很容易~)
看板C_and_CPP
標題Re: [問題] 不定數窮舉方法
時間Wed May 6 14:13:18 2009
※ 引述《henry035 (Rex)》之銘言：
: 假設要窮舉 n 個字母的組合， n 是一個變數，
: 我原本想用迴圈，但由於 n 是個不定值，因此無法預知要用幾層迴圈，
: 想請問這類型的問題有什麼方法可解呢？ 是不是有特定的演算法可使用呢？
: 我是有猜測是不是要用遞迴，但不太會用遞迴想方法(程式) ... @@|||
我手邊有類似的資料 給你參考看看
==============================
題目：給你 N 個數，請你列出這 N 個數的所有排列。
輸入輸出說明：先輸入一個正整數 N，代表後面有 N 個整數，請你以每一種排列一行的
方式將所有排列都印出來。
輸入1：3 1 2 3
輸出1：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
輸入2：4 1 3 5 7
輸出2：
1 3 5 7
1 3 7 5
1 5 3 7
1 5 7 3
1 7 3 5
1 7 5 3
3 1 5 7
3 1 7 5
3 5 1 7
3 5 7 1
3 7 1 5
3 7 5 1
5 1 3 7
5 1 7 3
5 3 1 7
5 3 7 1
5 7 1 3
5 7 3 1
7 1 3 5
7 1 5 3
7 3 1 5
7 3 5 1
7 5 1 3
7 5 3 1
參考程式：(不考慮重覆數字的情況)
#include <cstdlib>
#include <iostream>
#define MAX 30
using namespace std;
int s[MAX], v[MAX], r[MAX], n;
void Permutation(int index)
{
int i;
if ( index==n )
{
for (i=0; i<n; i++)
cout << s[r[i]] << " ";
cout << endl;
return;
}
for (i=0; i<n; i++)
{
if ( v[i] ) continue;
v[i]=1;
r[index]=i;
Permutation(index+1);
v[i]=0;
}
}
int main(int argc, char *argv[])
{
int i;
while (1)
{
cin >> n;
if ( n==0 ) break;
for (i=0; i<n; i++)
{
cin >> s[i];
v[i]=0;
}
Permutation(0);
}
system("PAUSE");
return EXIT_SUCCESS;
}
--
◢████◣ 其實，我平常就像其他女孩子一樣，靜靜的，很溫柔……
★▃ ★▃ ╯
～●────●～
◢██████◣
██████
◥ ◤ ψRikakoWoods
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.244.54.130
1F：推 sunneo:cout那部份如果改成coroutine中斷 就可以是一個簡易的 05/06 16:27
2F：→ sunneo:next_permutation , 可以以此取得中間結果 05/06 16:27
3F：推 henry035:謝謝原PO與樓上的資料與解說 05/06 17:15