

例えば, 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. それ以前にこの「数え上げ」は正しいでしょうか。

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


CC BY-SA 4.0
2023-02-17T13:44:08.087
93897
2023-03-15T05:37:53.543
35515
question
アルゴリズム
相異なるn個の数を並べたときの部分単調増加/減少数列で最長なものの長さを調べて分布を確認したい


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

[code]

    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)
    
[/code]

[code]

    N = 10, sum = 3628800
    [0, 0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]
    
[/code]


CC BY-SA 4.0
2023-03-15T05:37:53.543
94185
2023-03-15T05:37:53.543
54588
93897
answer