1

与えられた a 順列の階乗ベース表現(別名「カントール展開」)を計算するための効率的なアルゴリズムを探していnます。

「効率的」とは、実行時間よりも優れていることを意味します。O(n2)

(ところで、順列を階乗ベースの表現にマッピングする自然な方法は複数あり、採用されている規則のみが異なり、探しているアルゴリズムは、選択した特定の規則にある程度依存することを認識しています。現時点では、私はこの問題に強い好みはありませんが、これは主に、ある規則セット用に作成されたアルゴリズムは、実行時間に悪影響を与えることなく、別の規則セットをサポートするアルゴリズムに簡単に変換されるという証明されていない仮定に基づいています。)

FWIW、リストの順列の階乗基底表現を計算するための時間アルゴリズムの例は、 -間の (指定された順列での) 反転の数などの表現の- 番目の桁を計算するアルゴリズムです。順列内の th 要素と後続の要素。O(n2)(0, 1, ..., n-1)id_ii

または、疑似コードでは (0 ベースの配列を想定):

function FACTORIAL_REPRESENTATION(p):
    n <- length(p)
    d <- zeros(n - 1)
    for i <- 0 to n - 3:
        for j <- i + 1 to n - 2:
            if p[i] > p[j]:
                d[i] <- d[i] + 1
    return d

たとえば、順列 [2, 3, 1, 0] が [0, 1, 2, 3] の場合、上記の関数は反転に対応する配列 [2, 2, 1] を返す必要があります。

  • 2 : [ 2 , 3, 1 , 0], [ 2 , 3, 1, 0 ]
  • 2 : [2, 3 , 1 , 0], [2, 3 , 1, 0 ]
  • 1 : [2, 3, 1 , 0 ]

反転のカウントはソートに似ているように思えます。また、ソートは で実行できるため、これを行うためO(nlogn)のアルゴリズムが少なくとも存在する可能性があると思いますが、O(nlogn)思いつきませんでした。

4

1 に答える 1

1

あなたのループ

    for j <- i + 1 to n - 2:
        if p[i] > p[j]:
            d[i] <- d[i] + 1

は単なるランク クエリです。thのp後の の要素の数が より小さいことを知りたいとします。通常の操作に加えて、要素のランクを対数時間で報告するように平衡二分探索木を変更できます。このようなツリーを初期化して、 のすべてを含めることができます。次に、に設定して削除しています。(ループを逆方向に実行して、削除の代わりに挿入を行うこともできます。)ip[i]pd[i]rank(p[i])p[i]

于 2013-08-04T14:20:44.317 に答える