Burnling's Blog
0%

全排列

发表于 更新于
  • 因为全排列好像一直都没太明白（虽然可以用next_permutation）正好作业里有就顺便记录一下

引入

  • 我们都知道，如果是固定个数个全排列，比如1,2,3的全排列，我个人认为最简单的方法是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int n = 3;
    for(int a = 1;a<=n;a++){
        for(int b = 1;b<=n;b++){
            for(int c = 1;c<=n;c++){
                if(a==b||b==c||a==c)continue;
                printf("%d %d %d",a,b,c);
            }
        }
    }

    套三层循环的意义是，一共有三个位置需要排数，每层循环控制一位上的数字

    第5行的if就是用来判断有没有重复的数字，有就跳过

  • 那么如果是n个数的全排列呢？

    n个数的全排列，就有n位需要填数字，也就是说，需要n层的循环

    但是我们正常没办法写出不定层数的循环

    这个时候就需要递归了

循环层数的控制

  • 如果我们在函数体中写一个循环，在循环体中写一个自调用，那么每进入一次函数，都相当于是循环多了一层

    1
    2
    3
    4
    5
    6
    7
    8
    int x=2;
    void f(int n){
        if(n==x) return;
        for(int i = 0;i<x;i++){
            f(n+1);
        }
    }
    f(0);

    上面这个函数可以变为

    1
    2
    3
    4
    5
    6
    int x = 2;
    void f(0){
        for(int i = 0;i<x;i++){
            f(1);
        }
    }

    再进一步

    1
    2
    3
    4
    5
    6
    7
    8
    int x = 2;
    void f(0){
        for(int i = 0;i<x;i++){
            for(int j = 0;j<x;j++){
                ...
            }
        }
    }

    至此，我们就可以通过递归来控制循环的层数了

去重

  • 我个人认为，递归函数各层之间似乎不是很容易通信，所以我使用了一个数组传来传去以记录填过的数字

  • 既然我们之前定义了一个变量n以记录当前循环层数，那么这个n其实就是当前排列的第n项（见引入部分的代码）

  • 那么我们就可以向这一位填入数字，但是填入数字前需要检查这个数字有没有使用过，所以我写了一个Used函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool isUsed(int A[],int x,int t){
    	for(int i = 0;i<x;i++){
    		if(A[i]==t) return true;
    	}
    	return false;
    }
    int f(int A[],int x){
    	if(x == n){
    		//输出
    		return 0;
    	}
    	for(int i = 1;i<=n;i++){
    		if(isUsed(A,x,i)) continue;
    		A[x] = i;
    		f(A,x+1);
    	}
    }

递归边界

  • 如果已填位数等于总位数，即为这个排列已经排完了，需要输出

完整代码