差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:inversion [2018/05/28] – [転倒数の求め方] ikatakos | programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
* [[wpjp> | * [[wpjp> | ||
- | 具体的な例でイメージすると、$\{3,10,1,8,5\}$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。 | + | 具体的な例でイメージすると、$(3,10,1,8,5)$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。 |
これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。 | これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。 | ||
行 12: | 行 12: | ||
3 10 | 3 10 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
1 | 1 | ||
+ | × | ||
1 | 1 | ||
行 24: | 行 29: | ||
数列の各要素について、独立に考えることが出来る。 | 数列の各要素について、独立に考えることが出来る。 | ||
- | つまり、「自分より右にある、自分より小さな数の個数」を、全要素求めて足し合わせると、それが転倒数となる。 | + | つまり、「自分より右にある、自分より小さな数の個数」を全要素求めて足し合わせると、それが転倒数となる。 |
3→ 10 | 3→ 10 | ||
行 33: | 行 38: | ||
1+3+1 = 5 | 1+3+1 = 5 | ||
- | また、「自分より左にある、自分より大きな数の個数」でも同じ事である。 | + | また、「自分より左にある、自分より大きな数の個数」でも同じ。 |
3 | 3 | ||
行 44: | 行 49: | ||
[[programming_algorithm: | [[programming_algorithm: | ||
- | BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造である。 | + | BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造だ。 |
- | * 数列$\{a_1, | + | * 数列 $(a_1, |
* 以下の2つの要求を処理する | * 以下の2つの要求を処理する | ||
- | * '' | + | * '' |
- | * '' | + | * '' |
これを用いて、以下のように算出する。 | これを用いて、以下のように算出する。 | ||
===BITを用意=== | ===BITを用意=== | ||
- | まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。 | + | |
+ | まず、数列の最大値以上のサイズのBITを用意する。 | ||
+ | |||
+ | 最大値がわかっている必要がある。 | ||
+ | |||
+ | 最大値が大きすぎると、数列の要素自体は疎でも、BITにおける計算に時間がかかってしまう。\\ | ||
+ | そのような場合は、数列の要素を事前に小さい順に $1,2,3,...$ に対応づけて圧縮してもよい。\\ | ||
+ | すると数列の長さ $N$ が最大値の上限となる。\\ | ||
+ | 転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。 | ||
===数列を先頭から順番に処理する=== | ===数列を先頭から順番に処理する=== | ||
- | $i$ 番目(1-indexed)の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。 | ||
- | ==BITに加算する== | + | $i$ 番目(0-indexed)の項を |
- | $ADD(p_i, 1)$(BITの $p_i$ の位置に、1を加算する) | + | |
==自分より左にある自分より大きい数の個数を求める== | ==自分より左にある自分より大きい数の個数を求める== | ||
- | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | ||
- | 自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$(BITで $1$~$p_i$ の和)を求めることで得られる。 | + | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。\\ |
+ | その個数の総和は $i$ である。 | ||
- | 逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ | + | 自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$($p_1~p_i$ の和)を求めることで得られる。 |
+ | |||
+ | 逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ | ||
数列の各要素につきこれを足し合わせることで、転倒数が得られる。 | 数列の各要素につきこれを足し合わせることで、転倒数が得られる。 | ||
+ | |||
+ | ==BITに加算する== | ||
+ | |||
+ | $i+1$ 以降のために、BITの $p_i$ の位置に $1$ を加算する | ||
+ | |||
+ | * $ADD(p_i, 1)$ | ||
<sxh python> | <sxh python> | ||
行 95: | 行 115: | ||
for i, p in enumerate(ppp): | for i, p in enumerate(ppp): | ||
+ | ans += i - sum(p) | ||
bit.add(p, 1) | bit.add(p, 1) | ||
- | ans += i + 1 - sum(p) | ||
print(ans) | print(ans) | ||
</ | </ | ||
+ | |||
+ | === 末尾からでもよい === | ||
+ | |||
+ | 数列を末尾から処理してもよい。($i=N-1, | ||
+ | |||
+ | その場合、各 $i$ におけるBITの $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。 | ||
+ | |||
+ | |||
+ | ===== バリエーション ===== | ||
+ | |||
+ | ==== 同じ要素を含む場合 ==== | ||
+ | |||
+ | 転倒の定義が「$i \lt j$ なのに $A_i \gt A_j$ となっている $(i,j)$ ペア」なので、 | ||
+ | 転倒数に $A_i=A_j$ のペアは含まない。 | ||
+ | |||
+ | バブルソートの交換回数においても、同じ要素は交換しても状況が何も変わらないので行う必要は無く、最小回数には入らない。 | ||
+ | |||
+ | つまり、(転倒数自体とは関係ない話題だが)ソートする前と後とで同じ要素内の順番は変わらない。 | ||
+ | |||
+ | ソート前 | ||
+ | | , | ||
+ | | | , | ||
+ | v v v | ||
+ | ソート後 | ||
+ | |||
+ | 転倒数を求める上では、(同じ数字を含まない場合でも変わらないが、今一度)境界に注意。 | ||
+ | |||
+ | 上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、 | ||
+ | $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。 | ||
+ | |||
+ | |||
+ | ==== 文字列 ==== | ||
+ | |||
+ | '' | ||
+ | |||
+ | これも転倒数に言い換えられる。 | ||
+ | |||
+ | ソート後の文字列の左から出てくる順に $1,2,3,...$ と番号を振り、これに対応するようにソート前も置き換える。 | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | 16 5 3 13 2 6 8 9 4 14 15 1 7 11 10 12 ←これの転倒数を求めればよい | ||
+ | |||
+ | 「同じ要素を含む場合」で述べたように、ソート前後で同じ要素内の順番は変わらないので、同じ文字同士は「これは何個目の" | ||
+ | |||
+ | |||
+ | ==== 先読み不可 ==== | ||
+ | |||
+ | 数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、 | ||
+ | |||
+ | BITの代わりに平衡二分探索木等を使うと、値の上限を気にせずここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。 | ||
+ | |||
+ |