题目 94 递归实现排列型枚举

题目 94 递归实现排列型枚举

把 1∼n1∼� 这 n� 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n�。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤91≤�≤9

输入样例：

3
1

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1
2
3
4
5
6

主要思路

依次枚举每个位置放哪个数

递归搜索树

类似贪心的思想，每一个分支都是按字典序最小的来

与上一题区别

这一题与上一题区别在于构建递归搜索树时，上一题是每个位置来不来，这一题是每个位置的选择依次减少

上一题分支的思想体现在

    /*遍历左子树, 左子树是当前位置没选*/
    State[pos] = 0;
    dfs(pos + 1, totalNum);
    /*遍历右子树，当前位置选*/
    State[pos] = 1;     //其实这里有回溯的思想
    dfs(pos + 1, totalNum);
1
2
3
4
5
6

当前来不来有两个选择，所以有两个分支

本题分支用循环体现，最多有3选择，最少有1个选择

    for(int i = 1; i <= n; i++) {
        if(IsVisit[i] == false) {
            Num[pos] = i;
            IsVisit[i] = true;
            dfs(pos + 1, n);
            Num[pos] = 0;
            IsVisit[i] = false;
        }
    }
1
2
3
4
5
6
7
8
9

共同点是在一个分支遍历完后都需要回溯

代码

版本一：递归搜索树

#include 
#define MAX_NUM 10
int Num[MAX_NUM];
int IsVisit[MAX_NUM];
void dfs(int pos, int n) {
    if(pos > n) {
        for(int i = 1; i <= n; i++) {
            printf("%d ", Num[i]);
        }
        printf("\n");
        return;
    } 

    for(int i = 1; i <= n; i++) {
        if(IsVisit[i] == false) {
            Num[pos] = i;
            IsVisit[i] = true;
            dfs(pos + 1, n);
            Num[pos] = 0;
            IsVisit[i] = false;
        }
    }
} 
int main() {
    int n;
    scanf("%d", &n);
    dfs(1, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

版本二：库函数next_permutation(投机取巧)

#include 
using namespace std;
#define MAX_NUMS 10
int main() {
    int n;
    scanf("%d", &n);
    vector num;
    for(int i = 1; i <= n; i++) {
        num.push_back(i);
    }
    do {
        for(int i = 0; i < n; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
    }while(next_permutation(num.begin(), num.end()));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18