全排列问题

发表于 阅读次数：

TODO写的很差，需要重写

问题

在写OS作业的时候，银行家算法检查安全序列需要用到全排列，所以来写一下。题目如下：

  • 给定一个没有重复数字的序列，返回其所有可能的全排列。
1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]

思路

  • 我们把在纸笔上写的时候，通常会分情况写。
    1
    2
    3
    4
    5
    6
    7
    8
    1 2 3
    1 3 2

    2 1 3
    2 3 1

    3 1 2 
    3 2 1

把每一个值作为开头的情况都分类写出来。
我们可以把这种写法进行推广

可以发现，以某一值开头的情况，是把开头值除去之后的序列的全排列。

如

1
2
3
4
5
6
7
8
9
1 2 3 4

1开头的情况
1 2 3 4
1 2 4 3
1 3 2 4 
1 3 4 2
1 4 2 3
1 4 3 2
  • 其中 234、243、324、342、423、432是数列234的全排列

看到这，可以想到用递归的方式来完成。现在想想代码怎么实现。

  1. 我们要让序列中每一个元素都做一次开头，也就是要把每个元素的和开头位交换
  2. 交换之后，就是进入以X开头的情况了，用除去X的子序列进行递归
  3. 注意，我们需要每个元素的和开头位换回去，防止重复。

TODO

实现

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
30
void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void printArray(int a[], int n) {
    for(int i = 0; i < n; i++) {
        printf("%d",a[i]);
    }
    printf("\n");
}
//全排列 leetcode 46
//由start到end的全排列
void all_sequence_origin(int nums[],int start, int end) {

    //递归结束
    if(start == end) {
        printArray(nums, end + 1);
    }else {
        for(int i = start; i <= end; i++) {
            //每个人都要当序列的开头
            swap(nums,start,i);
            //求后面子序列的全排列
            all_sequence_origin(nums,start+1,end);
            //把序列还原，防止变序产生重复
            swap(nums,start,i);
        }
    }
}