[C++知识库]递归调用--排列的穷举

题目：从数字1~n中选取r个数字并将其排列，输出所有的排列结果，顺序不同也视为不同的排列。其中n和r为输入的参数：

例如：从数字1~5中选取3个数字时的排列为如下的60中情况：

1 2 3, 1 2 4, 1 2 5, 1 3 2, 1 3 4, 1 3 5, 1 4 2, 1 4 3, 1 4 5, 1 5 2, 1 5 3, 1 5 4,
2 1 3, 2 1 4, 2 1 5, 2 3 1, 2 3 4, 2 3 5, 2 4 1, 2 4 3, 2 4 5, 2 5 1, 2 5 3, 2 5 4,
3 1 2, 3 1 4, 3 1 5, 3 2 1, 3 2 4, 3 2 5, 3 4 1, 3 4 2, 3 4 5, 3 5 1, 3 5 2, 3 5 4,
4 1 2, 4 1 3, 4 1 5, 4 2 1, 4 2 3, 4 2 5, 4 3 1, 4 3 2, 4 3 5, 4 5 1, 4 5 2, 4 5 3,
5 1 2, 5 1 3, 5 1 4, 5 2 1, 5 2 3, 5 2 4, 5 3 1, 5 3 2, 5 3 4, 5 4 1, 5 4 2, 5 4 3

解题：

#include <stdio.h>
/* n的最大值 */
#define N_MAX (100)
/* 若数字已被使用，则将下标为该数字的元素设成1 */
int used_flag[N_MAX + 1];
int result[N_MAX];
int n;
int r;
void print_result(void)
{
    int i;
    for (i = 0; i < r; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}
void permutation(int nth)	// 参数nth表示当前正在处理第几个数字
{
    int i;
    if (nth == r) {
        print_result();
        return;            // 注意这里返回的位置在哪
    }
    for (i = 1; i <= n; i++) {
        if (used_flag[i] == 0) {
            result[nth] = i;
            used_flag[i] = 1;
            permutation(nth + 1);
            used_flag[i] = 0;
        }
    }
}
int main(int argc, char **argv)
{
    sscanf(argv[1], "%d", &n);
    sscanf(argv[2], "%d", &r);
    permutation(0);	
}

Linux下执行输出如下：

gcc permutation.c -o permutation
./permutation 3 3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

?

阅读世界，共赴山海

423全民读书节，邀你共读