全排列

coding>C++
973 词

题目描述

输入一个自然数N$（1<=N<=9）$，从小到大输出用1~N组成的所有排列，也就是说全排列。

例如：输入3，则输出

123

132

213

231

312

321

输入

1
输入一个自然数N(1<=N<=9)

输出

1
N的全排列，每行一个

样例输入

1
2

样例输出

1
2
12
21

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int a[9], n;
bool book[9];
void DFS(int k) {
    if (k >= n) {
        for (int i = 0; i < n; i++) cout << a[i];
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (book[i]) continue;
        book[i] = true;
        a[k] = i + 1;
        DFS(k + 1);
        book[i] = false;
    }
}
int main() {
    cin >> n;
    DFS(0);
    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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'

int main() {
    int n;
    cin>>n;
    vector<int> a;
    for(int i=1;i<=n;++i){
        a.push_back(i);
    }
    for(int i=0;i<n;++i){
        cout<<a[i];
    }
    cout<<endl;
    while(next_permutation(a.begin(),a.end())){
        for(int i=0;i<n;++i){
            cout<<a[i];
        }
        cout<<endl;
    }
    return 0;
}