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