公開日 :
更新日 :

逆順列

順列 \(P\) の「位置 → 値」の矢印を逆向きにした「値 → 位置」の対応が逆順列。
\(Q[P[i]] = i\) の \(1\) 行で \(O(N)\) で作れて、「値 \(v\) はどこにある？」に \(O(1)\) で答えられる。

定義

順列 \(P = (P_1, \dots, P_N)\) の逆順列 \(Q\) は、次を満たす順列。

  • \(Q_v = P\) の中で値 \(v\) がある位置
  • 式で書くと \(P_{Q_v} = v\)

たとえ話 : \(P\) は「座席 \(i\) に座っている人」、 \(Q\) は「人 \(v\) が座っている座席」。
同じ座席表を、座席から見るか、人から見るかの違い。

具体例

\(P = (3, 1, 4, 2)\)

位置 \(i\)\(1\)\(2\)\(3\)\(4\)
\(P_i\)\(3\)\(1\)\(4\)\(2\)

値 \(1\) は位置 \(2\)、値 \(2\) は位置 \(4\)、値 \(3\) は位置 \(1\)、値 \(4\) は位置 \(3\) なので、

\(Q = (2, 4, 1, 3)\)

確認 : \(P_{Q_1} = P_2 = 1\), \(P_{Q_2} = P_4 = 2\), \(P_{Q_3} = P_1 = 3\), \(P_{Q_4} = P_3 = 4\)

作り方

vector<int> Q(n + 1);
for (int i = 1; i <= n; i++) {
  Q[P[i]] = i;   // 値 P[i] の位置は i
}
  • 毎回 find で値を探すと 1 回 O(N)。何度も位置を聞くなら最初に逆順列を作る。
  • 0-indexed でも同じ形（Q[P[i]] = i）

性質

  • 逆順列の逆順列は元に戻る 矢印を \(2\) 回逆向きにすれば元通り。
    \(P_{Q_v} = v と Q_{P_i} = i\) は \(P\) と \(Q\) について対称で、
    「\(P\) と \(Q\) は互いに逆」という関係。
  • \(P\) の「位置の swap」は \(Q\) では「値の swap」
    \(P_x\) と \(P_y\)（中身 \(a, b\)）を入れ替えると、\(Q\) では \(Q_a\) と \(Q_b\) が変わるだけ。
    片方を更新しても、もう片方は \(2\) か所直せば済む。
  • 続けて適用すると恒等順列 \(P\) を適用してから \(Q\) を適用すると、すべての要素が元の場所に戻る。

問題文での書かれ方

「逆順列」という用語を使わず、条件式で定義することが多い。

書き方意味
\(P={P’_i} = i\) を満たす \(P’\)\(P’\) は \(P\) の逆順列
\(P’={P_i} = i\) を満たす \(P’\)同じく逆順列
\(P_j = i\) となる \(j\) を \(Q_i\) とする値から位置を引く、を言語化
\(i\) が \(P\) の何番目にあるか日常語よりの書き方

見抜くコツ： \(X_{Y_i} = i\) の形（添字の中に別の順列があって \(i\) に等しい）を見たら、\(X\) と \(Y\) は逆順列どうし。
コードでは \(Y[X[i]] = i\) に直せる。

メモ

「この操作を \(2\) 回やるとどうなる？」と自問する。
反転・補集合・逆順列・転置などは \(2\) 回で元に戻る。
こういう操作は実際に実行せず、フラグで「今どちらが本物か」を管理できないか疑う。

練習問題