すべての最長の減少シーケンスを出力する方法

cs.stackexchange https://cs.stackexchange.com/questions/1290

  •  16-10-2019
  •  | 
  •  

質問

$ n $の長さの整数の配列があるとします。最長のすべての減少シーケンスを出力するにはどうすればよいですか？ （サブシーケンスは、継続的である必要のない配列の要素で構成されています。たとえば、$（3,2,1）$は$（7,3,5,2,0,1）$のサブシーケンスの減少です。）最も長い減少シーケンスの長さを計算する方法は知っていますが、最長のすべての減少シーケンスを報告する方法を知りません。

Pseudocodeが役立ちます。

役に立ちましたか？

解決

次のシーケンスを入力と考えてください。

$$ n、n-2、n-1、n-3、n-5、n-4、n-6、n-8、n-7、n-9、....、n-3 cdot k -2、n -3 cdot k -1、n -3 cdot k -3、.... $$

簡単にすると、$ n = 3 cdot t + 1 $を想定してください。最長の減少サブシッケンス長は$ t $であり、長さ$ t $のサブシッケンスの減少数は$ 2^t $です。

したがって、利用可能なソリューションの数は$ theta（2^{n/3}）$です。しかし、なぜそうなのか、単にDAGでモデル化するだけで、$ a> b $と$ b $が元のシーケンスで$ a $の後に$ a $→$ b $からのエッジがあることに注意してください。

したがって、出力サイズは指数関数的である可能性があるため、最良の選択はDAGを作成し、DAGまたはすべての許容可能な方法を列挙する他の方法で最も長いパスを見つけることです。

他のヒント

- 再帰ヘルパー機能

    list form_longest_sublist_from(list array,list buffer,from) 
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i] 
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc

  • 関数を使用するアルゴリズム

    list of lists arrayoflongestlist
    list buffer;
    from i = length array - 1 to -1 step -1
        clear buffer
        add array[i] to buffer
        from x = i - 1 to -1 step -1
            if(array[x] < last buffer
                list sbuffer;
                sbuffer = form_longest_sublist_from(array,buffer,x);
                if length sbuffer > length buffer)
                    buffer = sbuffer;
                            endif
            endif
        endfor
            if length arrayoflongestlist > 0
                   if length (last arrayoflongestlist) < length buffer
                            clear arrayoflongestlist
                            add buffer to arrayoflongestlist
                   endif
                   else if length (last arrayoflongestlist) == length buffer
                add buffer to arrayoflongestlist
            endif

                   if length (last arrayoflongestlist) > i)
                break;
        else
            add buffer to arrayoflongestlist
        endif
    endfor

私は基本的に、アルゴリズム全体を問題に適合させるように再び反映しました。

基本的なアイデアは、アレイ内の各可能なポイント（各要素）から開始し、アレイの残りの部分を駆け抜けることでサブリストをすべて削減し、どの要素が小さくなっているかを確認し、それらの要素を使用して同じことを行う再帰を開始することです。その時点から開始する前に、後ろに与えられた最長のリストの再帰をフィルタリングします。

前述の私の最悪/ベストケースのシナリオは、このアルゴリズムを考慮して正しくない原因です。

すべての減少シーケンスについて、初期位置を別の配列に保存します。

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

これで、配列の温度には、すべての減少シーケンスの初期位置と最終位置が連続して含まれます。次に、それらを印刷します

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top