7.2 枚举排列(7.2 enumeration and arrangement)

有没有想过如何打印所有排列呢?输入整数n,按字典序从小到大的顺序输出前n个数的所有排列。两个序列的字典序大小关系等价于从头开始第一个不相同位置处的大小关系
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;
}

下面考虑程序实现,很明显序列A可以用数组表示,注意这边作者的构思最巧妙的地方在于S根本没必要出现,因为用一个参数记录当前所在位置,那么数组A后面的元素都是待排列的

代码实现如下

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); //递归调用 
	}
  
  }
}

循环变量i是当前考察的A[cur]。这边通过标志变量ok来实现对于i是否用过的检测

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