# 7.2 枚举排列(7.2 enumeration and arrangement)-其他

## 7.2 枚举排列(7.2 enumeration and arrangement)

eg:(1,3,2)<(2,1,3)，字典序最小的排列是(1,2,3,4,…,n)，最大的排列是(n,n-1,n-2,…,1)

7.2.1 生成1~n的排列

``````#include<iostream>
#include<algorithm>
using namespace std;

int n, v[100], ans[100];

void dfs(int p, int val[100]) {
if(p==n) {
for(int i = 0; i < n; i++) cout << ans[i] << " ";
cout << endl;
return;
}
for(int i = 0; i < n; i++) {
if(val[i]) {
ans[p] = val[i];
val[i] = 0;
dfs(p+1, val);
val[i] = i+1;
}
}
}

int main() {
cin >> n;
for(int i = 0; i < n; i++) v[i] = i+1;
dfs(0, v);
return 0;
}
``````

``````void print_permutation(int n, int* A, int cur) {
if(cur == n) {
for(int i = 0; i < n; i++) printf("%d ", A[i]);
printf("\n");
}
else for(int i = 1; i <= n; i++) { //尝试在A[cur]中填各种整数
int ok = 1;
for(int j = 0; j < cur; j++)
if(A[j]==i) ok = 0; //如果i已经在A[0]~A[cur-1]出现过，则不能再选
if(ok) {
A[cur] = i;
print_permutation(n, A, cur+1); //递归调用
}

}
}
``````

7.2.2 生成可重集的排列

————————

Have you ever thought about how to print all the permutations? Input the integer n and output all the permutations of the first n numbers in the order of dictionary order from small to large. The dictionary order size relationship of the two sequences is equivalent to the size relationship at the first different position from the beginning
eg:(1,3,2)< (2,1,3), the smallest arrangement of dictionary order is (1,2,3,4,…, n), and the largest arrangement is (n, n-1, n-2,…, 1)

7.2.1 generating 1 ~ n permutations

``````#include<iostream>
#include<algorithm>
using namespace std;

int n, v[100], ans[100];

void dfs(int p, int val[100]) {
if(p==n) {
for(int i = 0; i < n; i++) cout << ans[i] << " ";
cout << endl;
return;
}
for(int i = 0; i < n; i++) {
if(val[i]) {
ans[p] = val[i];
val[i] = 0;
dfs(p+1, val);
val[i] = i+1;
}
}
}

int main() {
cin >> n;
for(int i = 0; i < n; i++) v[i] = i+1;
dfs(0, v);
return 0;
}
``````

Next, considering the program implementation, it is obvious that sequence a can be represented by an array. Note that the most ingenious idea of the author here is that s is not necessary at all, because if the current position is recorded with a parameter, the elements behind array a are to be arranged

The code implementation is as follows

``````void print_permutation(int n, int* A, int cur) {
if(cur == n) {
for(int i = 0; i < n; i++) printf("%d ", A[i]);
printf("\n");
}
else for(int i = 1; i <= n; i++) { //尝试在A[cur]中填各种整数
int ok = 1;
for(int j = 0; j < cur; j++)
if(A[j]==i) ok = 0; //如果i已经在A[0]~A[cur-1]出现过，则不能再选
if(ok) {
A[cur] = i;
print_permutation(n, A, cur+1); //递归调用
}

}
}
``````

The cyclic variable I is a [cur] currently investigated. Here, the flag variable OK is used to detect whether I has been used

7.2.2 generating permutations of repeatable sets