排列算法

  |  

$1 枚举排列

以上两题为输出所有的排列,一个是有重复元素,一个是没有重复元素,

算法1:DFS,参考 枚举 中排列型枚举的部分。

可以处理重复元素。

算法2:字典序法 (next_permutation)

可以处理重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
sort(nums.begin(), nums.end());
do{
result.push_back(nums);
}
while(next_permutation(nums.begin(), nums.end()));
return result;
}
};

算法3:SJT算法

每个元素赋予一个方向,初始状态: $1(\leftarrow), 2(\leftarrow), 3(\leftarrow), …, n(\leftarrow)$

可移动数: 一个数指向一个比它小的数,该数是可移动数

1
2
3
4
step1: 找到最大的可移动数 m
step2: 交换 m 和 m 指向的数
step3: 改变所有比 m 大的数的方向
重复 step1~step3,直至找不到可移动数

不能处理重复元素

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
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
int n = nums.size();
vector<int> ori(n, 0); // 1 右,0 左
sort(nums.begin(), nums.end());
int minx = nums[0];
while(true)
{
result.push_back(nums);
int m = minx - 1;
int k = -1;
for(int i = 0; i < n; ++i)
{
if((i < n - 1 && ori[i] == 1 && nums[i + 1] < nums[i])
|| (i > 0 && ori[i] == 0 && nums[i - 1] < nums[i]))
{
if(nums[i] > m)
{
m = nums[i];
k = i;
}
}
}
if(k == -1)
break;
if(ori[k] == 0)
{
swap(nums[k], nums[k - 1]);
swap(ori[k], ori[k - 1]);
}
else
{
swap(nums[k], nums[k + 1]);
swap(ori[k], ori[k + 1]);
}
for(int j = 0; j < n; ++j)
{
if(nums[j] > m)
ori[j] ^= 1;
}
}
return result;
}
};

$2 下一个排列

算法:字典序法

A = 12345 为例

1) 从序列 A 的右端开始向左扫描,直至找到第一个比其右边数字小的数字 $A_{i}$,即 $i = \max\{j|a_{j} < a _{j+1}\}$。

2) 从 $A_{i}$ 右边找出所有比 $A_{i}$ 大的数中最小的数字 $A_{k}$,即 $A_{k} = \min\{a_{j}|a_{j} > a_{i},j > i\}$。

3) 交换 $A_{j}$ 与 $A_{k}$。

4) 将 $A_{i}$ 右边的序列翻转,即可得到字典序的下一个排列

5) 重复上面的步骤,直至得到字典序最大的排列,可以生成所有全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;
// 找到从 n-1 开始往左,第一个不单调不降的位置 t
int t = n - 2;
while(t >= 0 && nums[t] >= nums[t + 1])
--t;
if(t < 0)
reverse(nums.begin(), nums.end());
else
{
int k = n - 1;
while(k > t && nums[t] >= nums[k])
--k;
swap(nums[t], nums[k]);
reverse(nums.begin() + t + 1, nums.end());
}
}
};

$3 第 K 个排列

算法1:DFS

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
38
39
40
41
42
43
44
class Solution {
public:
string getPermutation(int n, int k) {
if(n == 1) return "1";
int result = 0;
// 第0个一定是 '1'
int path = 0;
int state = 0;
int deep = 0;
dfs(deep, path, 0, result, k, n, state);
return to_string(result);
}

private:
bool dfs(int& deep, int& path, int i, int& result, int k, int n, int& state)
{
// 已经产生 deep 个序列,当前序列已选 i 个数字
if(i == n)
{
++deep;
if(deep == k)
{
result = path;
return true;
}
else
return false;
}

for(int j = 1; j <= n; ++j)
{
if(!(((1 << j) & state))) // 数字 j 没选
{
path = path * 10 + j;
state |= (1 << j);
if(dfs(deep, path, i + 1, result, k, n, state))
return true;
path = (path - j) / 10;
state &= ~(1 << j);
}
}
return false;
}
};

算法2 : DFS + 剪枝

1
2
3
4
5
6
7
8
9
10
// 预处理阶乘
vector<int> factorials(n + 1, 1);
for(int i = 2; i <= n; ++i) factorials[i] = factorials[i - 1] * i;

// 已经选了 i 个数 还剩 n - i 个数,共 factorials[n - i] 种
if(deep + factorials[n - i] < k)
{
deep += factorials[n - i];
return false;
}

此剪枝非常有效

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
string getPermutation(int n, int k) {
if(n == 1) return "1";
vector<int> factorials(n + 1, 1);
for(int i = 2; i <= n; ++i) factorials[i] = factorials[i - 1] * i;
int result = 0;
// 第0个一定是 '1'
int path = 0;
int state = 0;
int deep = 0;
dfs(deep, path, 0, result, k, n, state, factorials);
return to_string(result);
}

private:
bool dfs(int& deep, int& path, int i, int& result, int k, int n, int& state, const vector<int>& factorials)
{
// 剪枝
// 已经选了 i 个数 还剩 n - i 个数,共 factorials[n - i] 种
if(deep + factorials[n - i] < k)
{
deep += factorials[n - i];
return false;
}
// 已经产生 deep 个序列,当前序列已选 i 个数字
if(i == n)
{
++deep;
if(deep == k)
{
result = path;
return true;
}
else
return false;
}

for(int j = 1; j <= n; ++j)
{
if(!(((1 << j) & state))) // 数字 j 没选
{
path = path * 10 + j;
state |= (1 << j);
if(dfs(deep, path, i + 1, result, k, n, state, factorials))
return true;
path = (path - j) / 10;
state &= ~(1 << j);
}
}
return false;
}
};

算法3: 阶乘数系统

阶乘数系统

阶乘数满足如下公式:

即 k 的值等于其各个位上的数字乘以其阶乘数之和

排列与阶乘数系统的映射

n 位阶乘数有 $n!$ 个,对应 $n!$ 种排列。例如 6 个 3 位阶乘数:

从阶乘构造全排列

排列编号 0 ~ N!-1,对于给定编号 k,首先将其用阶乘数系统展开,从左到右各个系数的含义就是输入数组中已使用元素的索引,用后将其从输入数组中删掉。

例如 N = 3,输入为 [1,2,3],k = 2, $k = 1 \times 2! + 0 \times 0! + 0 \times 0!$,系数为 (1,0,0),求 k 对应的排列的过程如下:

  • (1,0,0) 的第 1 个元素 1,nums=[1,2,3], nums[1] = 2, 因此 item.push_back(2),2 被使用,紧接着从 nums 删掉。
  • (1,0,0) 的第 2 个元素 0,nums=[1,3], nums[0] = 1, 因此 item.push_back(1),1 被使用,紧接着从 nums 删掉。
  • (1,0,0) 的第 3 个元素 0,nums=[3], nums[0] = 3, 因此 item.push_back(3),3 被使用,紧接着从 nums 删掉。

因此 k = 2 对应的排列为 213

给定 k 输出全排列的算法(与康托编码一致):输入为 n, k

1
2
3
4
5
6
构造 nums=[1,2,...,n]
while(!nums.empty())
看 k 的阶乘数系统展开的第一项的系数 idx
排列的下一位为 nums[idx]
删除 nums[t]
k -= idx * factorials[nums.size()]; // idx * 剩余nums长度的排列个数

以上算法的实现

1
2
3
4
5
6
7
8
9
vector<int> nums(n, 0);
for(int i = 0; i < n; ++i) nums[i] = i + 1;
for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
int idx = k / factorials[i];
k -= idx * factorials[i];
ans = ans * 10 + nums[idx];
nums.erase(nums.begin() + idx);
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 阶乘数系统
// 从高位往低位选
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> nums(n, 0);
for(int i = 0; i < n; ++i) nums[i] = i + 1;
vector<int> factorials(n, 1);
for(int i = 1; i < n; ++i) factorials[i] = factorials[i - 1] * i;

// fit k in the invertal 0 .. (n! - 1)
--k; // 从零计数
int ans = 0;
for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
int idx = k / factorials[i];
k -= idx * factorials[i];
ans = ans * 10 + nums[idx];
nums.erase(nums.begin() + idx);
}
return to_string(ans);
}
};
  • 用阶乘数系统枚举无重复全排列
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
38
39
40
41
42
43
44
45
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
int n = nums.size();
factorials = vector<int>(n + 1, 1);
for(int i = 1; i <= n; ++i) factorials[i] = factorials[i - 1] * i;
for(int k = 1; k <= factorials[n]; ++k)
{
vector<int> p = getPermutation(n, k);
vector<int> item;
for(int i: p) item.push_back((nums[i - 1]));
result.push_back(item);
}
return result;
}

private:
vector<int> factorials;

vector<int> getPermutation(int n, int k) {
vector<int> nums(n, 0);
for(int i = 0; i < n; ++i) nums[i] = i + 1;

// fit k in the invertal 0 .. (n! - 1)
--k; // 从零计数
int ans = 0;
for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
int idx = k / factorials[i];
k -= idx * factorials[i];
ans = ans * 10 + nums[idx];
nums.erase(nums.begin() + idx);
}
vector<int> result;
while(ans)
{
result.push_back(ans % 10);
ans /= 10;
}
reverse(result.begin(), result.end());
return result;
}
};

算法4: 康托编码

康托展开是一个全排列到自然数的双射。常用于构建哈希表的空间压缩。

  • 康托展开:给定一个 n 位全排列,确定其是字典序的第几个全排列
  • 逆康托展开:改订一个全排列的所有字符以及某个字典序号,得相应的全排列

给定全排列求字典序的过程

2341 为例,初始 rank = 0

  • step1: 第 1 位是 2,即所有 1 开头的在前面,rank += 1 * 3! = 6
  • step2: 第 2 位是 3,即所有以 1,2 作第 2 位的在前面,但是 2 已用,rank += 1 * 2! = 8
  • step3: 第 3 位是 4,即所有以 1,2,3 作第 3 位的在前面,但是 1,2 已用,rank += 1 * 1! = 9
  • step4: rank += 0 * 0! = 9

综上总结康托展开公式(rank 是从 0 开始计的。最后要加 1):

康托展开公式与阶乘数系统的公式一致。

$order(a_{i})$ 为 $a_{i+1}…a_{n}$ 中小于 $a_{i}$ 的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> factorials(n + 1, 1);
for(int i = 2; i <= n; ++i) factorials[i] = factorials[i - 1] * i;

int cantor_unfolds(const vector<int>& p)
{
int n = p.size();
int rank = 0;
for(int i = 0; i < n; ++i)
{
int t = 0; //
for(int j = i + 1; j < n; ++j) // 这里可以线段树优化
if(p[j] < p[i])
++t;
rank += t * factorials[n - (i + 1)];
}
++rank;
return rank;
}

给定字典序求全排列的过程(康托编码)

康托展开公式与阶乘数系统的公式一致。因此算法与阶乘数系统一样。

对应上例,求字符集为 1234 的第 k=10 个全排列

  • step0: --k; 变为从 0 开始
  • step1: 9 / 3! 商 1 余 3, 首位选一个当前没用过的第2(商+1)小字符,即2,将2删除,134,k 更新为余数 3
  • step2: 3 / 2! 商 1 余 1, 首位选一个当前没用过的第2(商+1)小字符,即3,将3删除,14,k 更新为余数 1
  • step3: 1 / 1! 商 1 余 0, 首位选一个当前没用过的第2(商+1)小字符,即4,将4删除,1,k 更新为余数 0
  • step4: 最后一位无需判断

康托编码的代码逻辑与阶乘数系统一致。

1
2
3
4
5
6
7
8
9
10
// fit k in the invertal 0 .. (n! - 1)
--k; // 从零计数
int ans = 0;
for(int i = n - 1; i >= 0; --i) // 从高位往低位选
{
int idx = k / factorials[i];
k -= idx * factorials[i];
ans = ans * 10 + nums[idx];
nums.erase(nums.begin() + idx);
}

$5 排列的哈希

1
2
3
4
5
int cantor_unfolds(const vector<int>& p);
int hash(const vector<int>& p)
{
return cantor_unfolds(p);
}

Share