順列と置換

概要

順序の定義された集合 \(A=\{a_0,a_1,\ldots,a_{n-1}\}\) から \(\pi_k(a_k)=a_{i_k}\) という変換により生成した順列 \((a_{i_0},a_{i_1},\ldots,a_{i_{n-1}})\) を想定すると、\(\pi\) は集合 \(A\) からそれ自身への置換 (全単射) である。\(A\) 上のある置換 \(\pi\) に順列 \((\pi_0(a_0),\pi_1(a_1),\ldots,\pi_{n-1}(a_{n-1}))\) が対応することから、集合 \(A\) から生成される順列は \(A\) の置換と同一視される。

\(n\) 個の異なる要素が含まれている集合から \(k\) 個の要素を選択して順序付けられた配置を部分順列 (partial permutation) と呼び、可能な順列の数を \({}_n P_k=n(n-1)(n-2)\ldots(n-k+1)\) で表す。\(k=n\) のとき \({}_nP_n=n!\) の順列である。

任意の \(n\) 要素の順列をそれ自身に変換する操作 \((0,1,\ldots,n-1)\) を恒等順列 (identity permutation) と呼ぶ。

順列における辞書式順序 (lexicographical order) は、順列を構成する要素の大小に基づいて順列の大小を決定し、辞書の単語順と同様の昇順での並びである。辞書式順序は美的ではあるがそれを使うのに特に利点が無いことが多い [1]。

Table of Contents

1. 概要
2. 生成アルゴリズム
   1. 逐次更新法
   2. ランクとアンランク
   3. 実行例
3. 参考文献

生成アルゴリズム

順列の生成アルゴリズムは、ある集合に対して可能なすべての並べ替えを効率的に列挙する手法である。順列を生成するアルゴリズムは組み合わせ最適化や経路探索、暗号など多くの応用分野で重要な役割を果たす。

逐次更新法

次順列アルゴリズム (next permutation algorithm) は、ある順列を指定されたときに辞書式順序で次に相当する順列を生成するアルゴリズムである。C 言語の std::next_permutation() は次順列アルゴリズムを使って与えられた順列の辞書順での次の順列を生成する。次順序アルゴリズムを使ってある集合のすべての順列を生成する方法は次のようになる。

1. 最初の順列は集合の各要素を昇順にソートした状態から開始する。

2. 次の順列を取得する。

   1. 現在の状態の最右端から順に隣り合う 2 つの要素を参照し、最初に降順になっていない位置 \(k\) を見つける。すべての隣り合う 2 要素が降順になっている場合、現在の状態は辞書順で最後の状態であることを意味する。

   2. 再右端から順に、位置 \(k\) の要素より大きい要素の位置 \(j\) を探索して \(k\) と \(j\) の要素と入れ替える。

   3. 位置 \(k+1\) 以降の要素を逆順に並べる。

   例えば初期状態で \(\pi_0=(1,2,3)\) の順列は、最初のイテレーションで右端から見て \(2,3\) の並びが降順になっていないため \(2\) の位置 \(k=1\) が見つかり、右端から見て \(2\) より大きい \(3\) と入れ替えて \(\pi_1=(1,3,2)\) を生成する。2 回目のイテレーションでは右端から見て降順でない \(1,3\) の位置 \(k=0\) が見つかり右端から \(1\) より大きい \(2\) と入れ替えて \(k+2\) 以降を逆順に並べた \(\pi_2=(2,1,3)\) を生成する。

3. 上記 2. を繰り返してすべての順列を生成する。

function nextPermutation(p) {
  if (p.length < 2) {
    return false;
  }

  // 1. 右から左に走査し、最初に p[k] < p[k+1] となる位置 k を探す。すべての要素が p[k] < p[k+1] であれば辞書順で最後の順列。
  let k = p.length - 2;
  while (p[k] >= p[k + 1]) {
    if (k === 0) {
      return false;
    }
    k--;
  }

  // 2. k 以降で右から左に操作し、最小の p[j] > p[k] となる位置 j を探して p[k] と p[j] を入れ替える。
  let j = p.length - 1;
  while (j >= 0 && p[j] <= p[k]) {
    j--;
  }
  [p[k], p[j]] = [p[j], p[k]];

  // 3. k+1 以降を逆順にして次の順列にする。
  let left = k + 1;
  let right = p.length - 1;
  while (left < right) {
    [p[left], p[right]] = [p[right], p[left]];
    left++;
    right--;
  }

  return true;
}

このアルゴリズムによる各順列の生成にかかる計算量は \(O(n)\) である。

ランクとアンランク

ランク (rank) とは順列のそれぞれに割り当てられた \(0\) から \(n!-1\) 範囲の一意な整数である。ある順列から対応するランクを算出する関数 (全単射) をランク関数 (ranking function) と呼ぶ。反対に、あるランクから対応する順列を算出する関数をアンランク関数 (unranking function) と呼ぶ。ランクは辞書式順序の並びを示している必要はない。

例として、辞書式順序での並びの位置をランクとし、与えられた順列と一致するまで 0 から next_permutaion を繰り返して数え上げるランク関数が考えられる。ただしこれは一回の算出に \(O(n \times n!)\) の計算量となるため非常に効率が悪い。

順列において、ある位置 \(j \lt i\) において \(a_j \gt a_i\) となっていることを逆転 (inversion) と言う。順列 \((a_0,a_1,\ldots,a_{n-1})\) 上のある位置 \(j\) より左にある \(a_j\) より大きい要素の個数 (または \(j\) より右にある \(a_j\) より小さい要素の個数) を、位置 \(a_j\) に配置した並び \((b_0,b_1,\ldots,b_{n-1})\) を逆転ベクトル (inversion vector) または逆転表 (inversion table) と呼ぶ。例えば順列 \((3,1,2,0)\) は \(0\) の左に \(0\) より大きい要素が 3 つ存在し、\(1\) の左に \(1\) より大きい要素が 1 つ存在し、… と配置されているため、その逆転ベクトルは \((3,1,1,0)\) となる。また逆転ベクトルから元の順列を構築することもできる [3]。

逆転ベクトルは対応する順列を一意に決定することができる [3]。したがって逆転ベクトルを \([0,n!-1]\) 範囲の一意な数値に変換したものはランクである。逆転ベクトル \((b_0,b_1,\ldots,b_{n-1})\) からランク \(r\) への変換は式 (\(\ref{inv2rank}\)) のように \(O(n)\) で求めることができる (階乗は事前計算されているものとする)。\[ \begin{equation} r = \sum_{i=0}^{n-1} b_i \times (n-i-1)! \label{inv2rank} \end{equation} \] 例えば逆転ベクトル \((3,1,1,0)\) のランクは \(3\times 3!+1\times 2!+1\times 1!+0\times 0!=21\) となる。

ランク \(r\) から逆転ベクトルの変換はこの逆操作で、商と余剰をイテレーションすることで求めることができる。\[ \begin{equation} \left\{ \begin{array}{rclrcl} b_0 & = & \lfloor r/(n-1)! \rfloor, & m_0 & = & r \bmod (n-1)! \\ b_1 & = & \lfloor m_0/(n-2)! \rfloor, & m_1 & = & m_0 \bmod (n-2)! \\ \vdots \\ b_{n-1} & = & \lfloor m_{n-2}/0! \rfloor \end{array} \right. \end{equation} \] 例えばランク \(r=21\)、要素数 \(n=4\) の逆転ベクトルは \(b_0=\lfloor 21/3! \rfloor=3\), \(b_1=\lfloor 3/2! \rfloor=1\), \(b_2=\lfloor 1/1! \rfloor=1\), \(b_3=\lfloor 0/0! \rfloor=0\) で \((3,1,1,0\)) となる。

逆転の発生数を単純に数える方法では、逆転ベクトルの計算量は \(O(n^2)\) となるため、ランクやアンランクによる順列生成の計算量も \(O(n+n^2)\) となる。しかし [2] では \(O(n)\) で計算できるより効率的な手法を提案している。ランクやアンランクは階乗や乗除算を多用するため計算効率では逐次更新法に劣るが、より広いクラスの問題に適用できるという利点がある [1]。

以下は [2] で紹介されている \(O(n)\) のランク関数とアンランク関数である。

// 階乗の事前計算 (n≦18)
const FACTORIALS = ((max) => {
  let factorial = 1;
  const result = [factorial]; // 0! = 1
  for (let n = 1; /* */ ; n++) {
    factorial *= n;
    if (factorial > max) {
      break;
    }
    result.push(factorial);
  }
  return result;
})(Number.MAX_SAFE_INTEGER);

// 順列のランクを基に元の順列を復元する関数
function unrank(r, n) {
  const p = Array.from({
    length: n
  }, (_, i) => i); // 恒等順列 [0, 1, ..., n-1]
  for ( /* */ ; n > 0; n--) {
    const s = Math.floor(r / FACTORIALS[n - 1]);
    [p[n - 1], p[s]] = [p[s], p[n - 1]];
    r %= FACTORIALS[n - 1];
  }
  return p;
}

//  順列のランクを計算する関数 (p は書き換えられる)
function rank(p) {
  const pinv = new Array(p.length); // 順列 p から逆順列 pinv を生成
  for (let i = 0; i < p.length; i++) {
    pinv[p[i]] = i;
  }

  let r = 0;
  for (let n = p.length; n > 1; n--) {
    const s = p[n - 1];
    [p[n - 1], p[pinv[n - 1]]] = [p[pinv[n - 1]], p[n - 1]];
    [pinv[s], pinv[n - 1]] = [pinv[n - 1], pinv[s]];
    r += s * FACTORIALS[n - 1];
  }
  return r;
}
console.log(rank([0, 2, 1, 3]));
console.log(unrank(21, 4));

実行例

参考文献

1. Steven S. Skiana. アルゴリズム設計マニュアル 下. 丸善出版 (2024)
2. MYRVOLD, Wendy; RUSKEY, Frank. Ranking and unranking permutations in linear time. Information Processing Letters, 2001, 79.6: 281-284.
3. KNUTH, Donald E. The Art of Computer Programming, Volume 3: Searching and Sorting. Reading MA: Addison-Wisley, 1973, 543-583.