algorithm - サブリニア メモリを使用した順列の生成

Question

N 個の要素の順列を生成するための十分に単純なアルゴリズムがあるかどうか疑問に思ってい1..NますO(N)。n 番目の順列を計算する必要はありませんが、すべての順列を計算できなければなりません。

もちろん、このアルゴリズムはある種のジェネレーターであるか、メモリを使用しない内部データ構造を使用する必要があります。O(N)サイズのベクトルとして結果を返すことは、Nサブリニア メモリの制限にすでに違反しているためです。

Answer 1

ランダム順列が一度に1つのエントリで生成されていると仮定しましょう。ジェネレーターの状態は、残っている要素のセットをエンコードする必要があります（完了するまで実行します）。したがって、可能性を排除できないため、ジェネレーターの状態は少なくともnビットです。

Answer 2

答えは「ノー」でなければならないと思います。

N要素順列のジェネレーターをステートマシンと見なします。少なくとも順列と同じ数の状態が含まれている必要があります。そうでない場合、すべての状態の生成が完了する前に繰り返しが開始されます。

Nあります！このような順列は、表現するために少なくともceil（log2（N！））ビットを必要とします。 スターリングの近似は、log2（N！）がO（N log N）であることを示しているため、劣線形メモリを使用してこのようなジェネレーターを作成することはできません。

Answer 3

C ++アルゴリズムnext_permutationは、シーケンスを次の順列にインプレースで再配置するか、falseそれ以上の順列が存在しない場合に戻ります。アルゴリズムは次のとおりです。

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) return false; // False for empty ranges.
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false; // False for single-element ranges.
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        // Find an element *n < *(n + 1).
        if (*i <*ii) {
            BidirectionalIterator j = last;
            // Find the last *m >= *n.
            while (!(*i < *--j)) {}
            // Swap *n and *m, and reverse from m to the end.
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        // No n was found.
        if (i == first) {
            // Reverse the sequence to its original order.
            reverse(first, last);
            return false;
        }
    }
}

これは、生成された順列ごとに一定のスペース（イテレーター）を使用します。あなたはそれを線形だと思いますか？

Answer 4

階乗数を使えばできるかもしれません。結果の順列を段階的に抽出できるため、結果全体をメモリに保持する必要はありません。

しかし、私がおそらく始めた理由は、階乗数自体のサイズの増加する動作が何であるかがわからないためです。32ビット整数などに収まる場合、Nは定数に制限されるため、O（N）はO（1）に等しくなるため、配列を使用する必要がありますが、どれくらいの大きさになるかはわかりませんN で表します。