全排列简介

最近打算把印象笔记记的笔记慢慢地写成博客的形式归档起来,也算是给自己的一个督促。

1.基础概念

这个概念最早接触是在高中时学oi在那本老旧的竞赛书上接触到的。抛出的问题类似于

写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba。。

排列和组合的区别就在于是否是有顺序的,全排列从字面上的意思就是列出所有元素的排列,其实这个直观的理解是没有错的。不过还是查一下网上的定义。

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式:全排列数f(n)=n!(定义0!=1)

以上就可以大概了解全排列是个什么东西了。那么直接上一版最简单的通过递归实现的全排列代码。

2.全排列递归实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> ans;

void allRange(vector<int>& nums, int k) {
int len = nums.size();
if (k == len - 1) {
ans.push_back(nums);
return;
}
else {
for (int i = k; i < len; ++i) {
swap(nums[k], nums[i]);
allRange(nums, k + 1);
swap(nums[k], nums[i]);
}
}
}

vector<vector<int>> permute(vector<int>& nums) {
allRange(nums, 0);
return ans;
}
};

具体解决的是LeetCode上P46.全排列问题

可以看到,代码中是一直在做交换。那么是如何交换的呢。可以简单用个例子展示一下,比如123。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以得出 全排列就是从第一个数字起每个数分别与它后面的数字交换。

这样一个简单的全排列解决方案就完成了。可是如果遇到元素结合里有重复元素,则会出现重复排列的情况。比如122,按照这个算法会出现多个重复的排列。

那么继续按照上面的思路,由于 __由于全排列就是从第一个数字起每个数分别与它后面的数字交换__,我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122,第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了,但对212,它第二个数与第三个数是不相同的,交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。

换种思维,对122,第一个数1与第二个数2交换得到212,然后考虑第一个数1与第三个数2交换,此时由于第三个数等于第二个数,所以第一个数不再与第三个数交换。再考虑212,它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。

这样我们也得到了在全排列中去掉重复的规则—— __去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换__。用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。下面给出一份示例代码:

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
31
32
33
34
35
36
37
class Solution {
public:
vector<vector<int>> ans;

bool isSwaped(vector<int>& nums, int begin, int end) {

for (int i = begin; i < end; ++i) {
if (nums[i] == nums[end]) {
return false;
}
}
return true;
}

void allRange(vector<int>& nums, int k) {
int len = nums.size();
if (k == len - 1) {
ans.push_back(nums);
return;
}
else {
for (int i = k; i < len; ++i) {
if (!isSwaped(nums, k, i)) {
continue;
}
swap(nums[k], nums[i]);
allRange(nums, k + 1);
swap(nums[k], nums[i]);
}
}
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
allRange(nums, 0);
return ans;
}
};

具体解决的问题是LeetCode上47. 全排列 II