2

例えば, 5つの数1,2,3,4,5を並び替えた3,1,5,2,4の場合, 単調増加な部分列で最長のものが1,2,4で単調減少な部分列で最長のものは3,1や3,2、5,2や5,4。したがってこの場合の最長なものの長さは3です。
そのままの1,2,3,4,5なら5となります。
「Erdös Szekersの定理」により, n^2+1個の相違なる数を並べ替えた場合, 必ずn以上の長さの単調増加か単調減少な部分列があるわけですが, それらの「長さ」の分布が気になって調べてみようとプログラムを組んで数えさせてみました。
普段プログラムはこのような「気になることを一寸調べる」程度でしか使わないので技術も知識も乏しく工夫のないプログラムになることが多くその上正しく動いているのかどうかも分からない場合があり, 今回もそのような感じです。

例えば, 3^2+1で10個の数を並び替えた場合の分布が
0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2
と出たのですが... 果たしてこれで良いのか。

rubyで組んで
[Done] exited with code=0 in 157.134 seconds
と少々時間が掛かり, これ以上は時間が相当掛かりそうです。

そこで質問です。

  1. 上手いアルゴリズム、プログラミングの手法があるでしょうか。
  2. それ以前にこの「数え上げ」は正しいでしょうか。

教えて下さると有難いです。

5
  • sum(0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2) == 3628800 == 10! なので、総数は合致していますね。
    – metropolis
    Commented 2023年2月17日 14:26
  • 流石にそこは... 一応rubyが順列の全てについて「数えて」いるので... (工夫がない... ) Commented 2023年2月18日 0:11
  • 1
    MacBookPro(Retina, 13-inch, Early 2015)2.7 GHz デュアルコアIntel Core i5で一晩回してもまだ12個の並べ替えの結果までしか出てません... Commented 2023年2月18日 0:14
  • [12, [0, 0, 0, 0, 25038288, 241860366, 169395678, 37886686, 4501774, 306682, 11882, 242, 2] Commented 2023年2月18日 0:14
  • 単調増加列に限れば en.wikipedia.org/wiki/Longest_increasing_subsequence から参照されている "On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations" (doi:10.1016/j.spa.2015.03.009) に漸近的な挙動について書かれているらしいというのを見つけたのですが、内容が自分には難しくて読み切れなかったのでコメントに残しておきます。
    – nekketsuuu
    Commented 2023年2月19日 12:25

1 件の回答 1

1

最長増加部分列(Longest Increasing Subsequence, LIS)を検索して見つけた 最長部分増加列(非連続) を読むと,Python では bisect -- Array bisection algorithm を使って実装できそうです。
下記に記述例を示しますが,LIS の長さを求める関数は記載されていた「コード例」は使わず「考え方」に記載のとおりに記述しました(今回の目的では結果は変わらないようです)。一方,最長減少部分列(Longest Decreasing Subsequence, LDS)の長さは,数列を逆順にしたものから同じ関数で求めました。なお,下記の記述例の計算時間は私の環境(macOS13.1(M1), Python 3.10.10)で約 7秒でした。

from bisect import bisect_left
from itertools import permutations


def lis(A):
    dp = []

    for a in A:
        idx = bisect_left(dp, a)
        if idx == len(dp):
            dp.append(a)
        else:
            dp[idx] = a

    return len(dp)


def lds(A):
    return lis(A[::-1])


N = 10
seq = list(range(1, N + 1))
result = [0] * (N + 1)

for p in permutations(seq, N):
    result[max(lis(p), lds(p))] += 1

print(f'N = {N}, sum = {sum(result)}')
print(result)
N = 10, sum = 3628800
[0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]
1
  • ありがとうございます。試してみよう♬ それにしても何故うまくいくのやろ。其処もよく吟味してみよう。 Commented 2023年3月16日 11:02

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。