排列⚓︎

排列（ $\text{Permutation}$ ）是指从一组元素中，按照一定的顺序选取全部或部分元素所形成的有序序列。排列强调元素的顺序，因此不同的顺序被视为不同的排列。

上一个排列与下一个排列⚓︎

求解一组长度为 $n$ 的数的上一个排列:

找到最大下标 $i$ ，满足 $s[i] < s[i - 1] (1 \le i < n)$
找到最大下标 $j$ ，满足 $\forall k \in [i, j]: s[k] < s[i - 1] (1 \le j < n)$
交换下标为 $i-1$ 和 $j$ 处的两个字符
将下标 $i$ 开始的后缀反转

上一个排列

C++

#include <algorithm>
#include <cstdint>
#include <vector>
using namespace std;

vector<int64_t> prev_permutation(vector<int64_t> nums) {
  int n = nums.size();
  int i = n - 1;
  for (; i >= 1; --i) {
    if (nums[i] < nums[i - 1]) { break; }
  }
  // 已经是字典序最小的排列，没有更小的排列, 返回字典序最大的排列
  if (i == 0) {
    reverse(next(nums.begin(), i), nums.end());
    return nums;
  }
  int j = i;
  for (; j < n; ++j) { // 找到最后一个比 nums[i-1] 小的数
    if (nums[j] < nums[i - 1]) { continue; }
    break;
  }
  j -= 1; // j 回退到最后一个满足条件的位置
  swap(nums[i - 1], nums[j]);
  reverse(next(nums.begin(), i), nums.end());
  return nums;
}

将上述算法中的比较式子不等号反转就能得到下一个排列:

下一个排列

C++

#include <algorithm>
#include <cstdint>
#include <vector>
using namespace std;

vector<int64_t> next_permutation(vector<int64_t> nums) {
  int n = nums.size();
  int i = n - 1;
  for (; i >= 1; --i) {
    if (nums[i] > nums[i - 1]) { break; }
  }
  // 已经是字典序最大的排列，没有更大的排列, 返回字典序最小的排列
  if (i == 0) {
    reverse(next(nums.begin(), i), nums.end());
    return nums;
  }
  int j = i;
  for (; j < n; ++j) { // 找到最后一个比 nums[i-1] 大的数
    if (nums[j] > nums[i - 1]) { continue; }
    break;
  }
  j -= 1; // j 回退到最后一个满足条件的位置
  swap(nums[i - 1], nums[j]);
  reverse(next(nums.begin(), i), nums.end());
  return nums;
}

康托展开⚓︎

康托展开（ $\text{Cantor Expansion}$ ）是一种将长度为 $n$ 的排列与 $n!$ 个整数之间建立双射关系的算法。
前者到后者称为康托展开，后者到前者称为逆康托展开（ $\text{Inverse Cantor Expansion}$ ）。

康托展开将一个排列映射到一个整数，该整数表示该排列在字典序中的排名，从0开始计数。

Example

排列 $[3,1,2]$ 的康托展开为 $4$ ，因为在所有排列中， $[1,2,3],[1,3,2],[2,1,3],[2,3,1]$ 都排在它前面

对于排列 $P = [p_1, p_2, \dots, p_n]$ ，康托展开公式为： $C(P) = \sum_{i=1}^{n} (c_i * (n-i)!)$ 。
其中 $c_i = \sum_{j=i+1}^{n} \mathbb{I}\left(p_j < p_i\right)$ ，表示在 $p_i$ 之后的元素中小于 $p_i$ 的元素个数。
利用树状数组或线段树可以在 $O(n \log n)$ 时间内计算康托展开。

【模板】康托展开

给定一个排列 $P = [p_1, p_2, \dots, p_n]$ ，求其康托展开 $C(P)$ 。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int64_t cantor_expansion(const vector<int> &permutation, int64_t mod = 998'244'353) {
  int n = permutation.size();
  vector<int64_t> fenwick(n + 1, 0);  // 树状数组, 用于维护已出现的元素

  auto fenwick_update = [&](int64_t index, int64_t delta) {
    while (index <= n) {
      fenwick[index] += delta;
      index          += index & -index;
    }
  };
  auto fenwick_query = [&](int64_t index) {
    int64_t sum = 0;
    while (index > 0) {
      sum   += fenwick[index];
      index -= index & -index;
    }
    return sum;
  };
  // 从后向前处理排列元素 (1)
  int64_t result = 0;
  int64_t factor = 1;  // (n-n)!
  for (int64_t i = n; i >= 1; --i) {
    int64_t x = permutation[i - 1];
    // 查询在 x 之前的元素中有多少个已经出现过 (即右边比 x 小的元素个数)
    int64_t ci = fenwick_query(x - 1);
    result     = (result + ci * factor % mod) % mod;  // 累加当前元素的贡献
    // 标记 x 已出现
    fenwick_update(x, 1);
    factor = factor * (n - (i - 1)) % mod;  // 更新 (n-i)!
  }

  return (result + 1) % mod;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> permutation(n);
  for (int i = 0; i < n; ++i) { cin >> permutation[i]; }
  cout << cantor_expansion(permutation) << "\n";
  return 0;
}

如果从前向后处理，需要预处理阶乘数组
树状数组需要先标记所有元素，查询完成后再取消标记

逆康托展开⚓︎

给定一个整数 $k$ ，求出字典序中排名为 $k$ 的排列。

对于排列 $P = [p_1, p_2, \dots, p_n]$ ，康托展开 $C(P) = \sum_{i=1}^{n} (c_i * (n-i)!)$ ，其中 $c_i$ 表示在 $p_i$ 之后的元素中小于 $p_i$ 的元素个数。
逆康托展开的过程就是从 $k$ 中逐步提取 $c_i$ 的过程，然后根据 $c_i$ 构造排列。
一般会先根据某个排列计算出真实排名，然后询问该排名之前或之后 $m$ 个排列。由于排名较大，因此需要使用阶乘进制来表示排名。

阶乘进制

阶乘进制每一位的权值依次为 $0!, 1!, 2!, 3!, \dots, n!$ 。
第 $i(i=0,1,2,\dots,n)$ 位对应权值 $i!$ ，取值范围为 $[0, i]$ 。
进位处理与十进制类似。

Example

十进制数 $463$ 转换为阶乘进制:
$463 = 3 * 5! + 4 * 4! + 1 * 3! + 0 * 2! + 1 * 1! + 0 * 0!$ ，因此阶乘进制表示为 $[3,4,1,0,1,0]$ 。

这个过程利用线段树（二分）可以在 $O(n \log n)$ 时间内完成。

火星人plus

给定一个排列 $P = [p_1, p_2, \dots, p_n]$ 和一个整数 $k$ ，求字典序中排名为 $C(P) + k$ 的排列。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct segment_tree {
  vector<int64_t> sum;  // sum[i] 表示该节点覆盖的区间内还未使用的元素个数

  explicit segment_tree(int64_t n) : sum(n * 4) {}

  // 建树, 根节点为 1, 覆盖区间 [1, n]
  void build(int64_t node, int64_t left, int64_t right) {
    if (left == right) {
      sum[node] = 1;  // 初始时每个元素都未使用
      return;
    }
    int64_t mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    sum[node] = sum[2 * node] + sum[2 * node + 1];
  };

  // 更新, 标记 index 位置的元素已使用
  void update(int64_t index, int64_t node, int64_t left, int64_t right) {
    if (left == right) {
      sum[node] = 0;  // 标记该元素已使用
      return;
    }
    int64_t mid = (left + right) / 2;
    if (index <= mid) {
      update(index, 2 * node, left, mid);
    } else {
      update(index, 2 * node + 1, mid + 1, right);
    }
    sum[node] = sum[2 * node] + sum[2 * node + 1];
  };

  // 查询区间和
  int64_t query(int64_t ql, int64_t qr, int64_t node, int64_t left, int64_t right) {
    if (ql <= left && right <= qr) { return sum[node]; }
    int64_t mid = (left + right) / 2;
    int64_t res = 0;
    if (ql <= mid) { res += query(ql, qr, 2 * node, left, mid); }
    if (qr > mid) { res += query(ql, qr, 2 * node + 1, mid + 1, right); }
    return res;
  };

  // 查询第 k 个未使用的元素, 并且标记该元素已使用
  int64_t query_kth(int64_t k, int64_t node, int64_t left, int64_t right) {
    if (left == right) {
      sum[node] = 0;  // 标记该元素已使用
      return left;
    }
    int64_t mid = (left + right) / 2;
    int64_t res;
    if (sum[2 * node] >= k) {  // 左子树的未使用元素个数足够, 继续往左子树找
      res = query_kth(k, 2 * node, left, mid);
    } else {  // 否则往右子树找, k 减去左子树的未使用元素个数
      res = query_kth(k - sum[2 * node], 2 * node + 1, mid + 1, right);
    }
    sum[node] = sum[2 * node] + sum[2 * node + 1];
    return res;
  };
};

void inverse_cantor_expansion(vector<int64_t> &permutation, int64_t k) {
  int64_t n = permutation.size();
  segment_tree tree(n);
  tree.build(1, 1, n);

  // 计算当前排列的康托展开排名
  for (int64_t i = 0; i < n; ++i) {
    int64_t x = permutation[i];
    if (x == 1) {
      permutation[i] = 0;
    } else {
      // 查询在 x 之前的元素中有多少个未使用
      permutation[i] = tree.query(1, x - 1, 1, 1, n);
    }
    tree.update(x, 1, 1, n);  // 标记 x 已使用
  }
  permutation[n - 1] += k;  // 对最后一个位置的 ci 值加上 k
  // 处理进位
  for (int64_t i = n - 1; i > 0; --i) {
    permutation[i - 1] += permutation[i] / (n - i);
    permutation[i]     %= (n - i);
  }

  // 重新建树, 用于根据 ci 值构造排列
  tree.build(1, 1, n);
  for (int64_t i = 0; i < n; ++i) {
    int64_t ci = permutation[i];
    // 查询第 ci+1 个未使用的元素，并标记该元素已使用
    permutation[i] = tree.query_kth(ci + 1, 1, 1, n);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, k;
  cin >> n >> k;
  vector<int64_t> permutation(n);
  for (int64_t i = 0; i < n; ++i) { cin >> permutation[i]; }
  inverse_cantor_expansion(permutation, k);
  for (int64_t i = 0; i < n; ++i) {
    if (i > 0) { cout << " "; }
    cout << permutation[i];
  }
  cout << "\n";
  return 0;
}

排列⚓︎

上一个排列与下一个排列⚓︎

康托展开⚓︎

逆康托展开⚓︎

评论