最長増加部分列(LIS)
リストから、左から右へ、前の数より大きい数を選んでいきます。このような鎖はどこまで長くなるでしょうか? パズルの本に載るほど単純な問いですが、その答えはトランプの一人遊び、古典的な動的計画法の表、そしてランダムなシャッフルに関する最も美しい結果の一つを結びつけます。
問題
数のリストが与えられたとき、部分列はそのうちのいくつかを元の順序のまま残したものです。各値が前の値より大きければ、その部分列は増加しています。最長増加部分列(LIS)は、そのような選び方のうち最も長いものです。n 個の値のリストには 2ⁿ 個の部分列があるので、すべてを調べる方法はごく短いリストでしか使えません。
表
len[i] を、ちょうど位置 i で終わる最長増加部分列の長さとします。これは、その値だけなら 1、値がより小さい前の位置 j については 1 + len[j] で、そのうち最も大きいものになります。各位置は前のすべての位置を振り返るので、表には n·(n − 1)/2 回の比較が必要です。答えは最大の len[i] で、各 len[i] をどの j が与えたかを記録しておけば、部分列をさかのぼって読み取れます。
例
3, 10, 2, 1, 20, 4, 6, 7, 5, 9 を考えます。位置ごとの長さは 1, 2, 1, 1, 3, 2, 3, 4, 3 と 5 です。20 は 3, 10 を延ばし、4 は 3 を延ばし、6 は 4 を、7 は 6 を、9 は 7 を延ばします。9 からさかのぼると 3, 4, 6, 7, 9 が得られ、これは長さ 5 の増加部分列です。
より速い方法:ペイシェンスソート
値をトランプのカードのように山に配ります。各値は、一番上のカードがその値より小さくない山のうち最も左の山に置くか、そのような山がなければ右に新しい山を作ります。山の数が LIS の長さです。山の一番上のカードは常に整列しているので、置くべき山は二分探索で見つけられ、方法全体は O(n log n) ステップで済みます。名前は、これに似たトランプの一人遊び(ペイシェンス、ソリティア)に由来します。
少しの数学
1935年、ポール・エルデシュとジョージ・セケレシュは、n² + 1 個の異なる数からなるどんなリストにも、長さ n + 1 の増加部分列か減少部分列があることを証明しました。1961年にはスタニスワフ・ウラムが、n 個の数をランダムにシャッフルしたときの LIS の長さを問いました。n が大きいとき 2√n に近いという答えは、1977年にアナトリー・ヴェルシクとセルゲイ・ケロフ、そしてベン・ローガンとラリー・シェップによって確かめられました。さらに1999年、ジンホ・バイク、パーシー・デイフト、クルト・ヨハンソンが、そのゆらぎの正確な形を突き止めました。ランダム行列理論に現れるトレイシー–ウィドム分布です。
試してみよう
アプリを開いて「ステップ」を押してください。オレンジ色の列は計算中の位置、青色の列はそれと比較している前の位置です。より長い並びが見つかるにつれて「長さ」の行が伸び、「直前の位置」の行はそれがどこから来たかを記録します。最後に答えがオレンジ色でさかのぼって読み取られ、表の下に表示されます。
よくある質問
LIS の時間計算量はどれくらいですか?
表を使うと O(n²) です。各位置が前のすべての位置を調べるからです。ペイシェンスソートと二分探索を使うと O(n log n) です。どちらも O(n) のメモリが必要です。
最長非減少部分列はどうやって求めますか?
値が等しい値の後に続けられるようにします。つまり < の代わりに ≤ で比較します。アプリでは「等しい値を許可」にチェックを入れます。ペイシェンスソートでは、各値を、一番上のカードがその値より真に大きい山のうち最も左の山に置きます。
最長減少部分列とは何ですか?
比較の向きを逆にした同じ問題です。あるいは、すべての値の符号を反転したリストの LIS です。エルデシュ–セケレシュの定理により、十分に長いリストには必ず長い増加部分列か長い減少部分列があります。
ランダムなリストの LIS はどのくらいの長さですか?
n 個の異なる数をランダムにシャッフルした場合、n が大きければ 2√n に近くなります。補正は n の6乗根のように増えるので、1000 個の数では平均は約 58 で、2√1000 ≈ 63 を少し下回ります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
最長増加部分列を試す