算法基础算法

排列算法

字数统计: 2.8k字   |   阅读时长: 13分
, ,

$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