[解決済み] 並べ換え→数→並べ換えの高速マッピングアルゴリズム

質問

n個の要素を持っています。 例として、7つの要素、1234567とします。 この7つの要素には7! = 5040通りの順列があり得ることが分かっています。

2つの関数からなる高速なアルゴリズムが欲しい。

f(number)は0から5039までの数を一意な順列に写像し

f'(permutation)は、順列を生成された番号にマッピングし直します。

各順列がそれ自身のユニークな番号を持っていれば、番号と順列の間の対応については気にしない。

ですから、例えば、以下のような関数があります。

f(0) = '1234567'
f'('1234567') = 0

思いつく最速のアルゴリズムは、すべての順列を列挙し、両方向のルックアップテーブルを作成することで、一度テーブルが作成されれば、f(0)はO(1)、f('1234567')は文字列に対するルックアップとなるでしょう。 しかし、これは特にnが大きくなったときにメモリを消費します。

どなたか、素早く動作し、メモリの欠点がない別のアルゴリズムを提案していただけませんか？

どのように解決するのですか？

n個の要素の並べ換えを記述するために、最初の要素が終わる位置は、n個の可能性があるので、0からn-1の間の数でこれを記述することができることがわかります。次の要素が終わる位置には、n-1 の可能性が残っているので、0 から n-2 の間の数でこれを記述することができます。

などと、n個の数字ができるまで続けます。

n = 5 の例として、次のような順列を考えてみましょう。 abcde を caebd .

• a は最初の要素ですが、2番目の位置で終わっているので、インデックス 1 .
• b は 4 番目の位置、つまりインデックス 3 で終了しますが、これは 3 番目に残ったものなので、これを 2 .
• c は最初に残った位置で終了し、それは常に 0 .
• d は最後に残った位置で終了し、それは (残り 2 つの位置のうち) 1 .
• e は唯一残った位置で終わり、そのインデックスは 0 .

つまり、インデックス配列 {1, 2, 0, 1, 0} .

これで、例えば2進数の場合、「xyz」は「z + 2y + 4x」を意味することがわかりました。10進数の場合は

は、z + 10y + 100xとなります。各桁に何らかの重みをかけて、その結果を合計する。重みの明らかなパターンはもちろん、重みはw = b^kで、bは数の底、kは桁のインデックスです。(私は常に右から桁を数え、一番右の桁はインデックス0から始めることにしています。同様に、私が「最初の」桁について話すとき、私は一番右の桁を意味します)。

は 理由 は、0 から k までの数字で表すことができる最も大きい数字が、k+1 の数字だけで表すことができる最も小さい数字よりちょうど 1 だけ小さくなければならないからです。2進数では、0111は1000より1低い数字でなければならない。10 進法では、099999 は 100000 よりも 1 つ小さい数字でなければなりません。

変数ベースへのエンコード

後続の数値の間隔がちょうど1であることが重要な規則です。これを理解した上で、インデックスの並びを 変数ベース番号 . 各桁の基数は、その桁の異なる可能性の量です。10進数の場合、各桁は10の可能性があり、このシステムでは右端の桁は1の可能性があり、左端の桁はnの可能性があります。しかし、右端の数字（数列の最後の数字）は常に0であるため、これを除外します。一般に、k番目の桁はb[k] = k + 2の底を持つことになります。k番目の桁に許される最大の値は、h[k] = b[k] - 1 = k + 1 です。

桁の重み w[k] についての我々の規則は、i が i = 0 から i = k になる h[i] * w[i] の合計が、1 * w[k+1] に等しいことを要求しています。再帰的に述べると、w[k+1] = w[k] + h[k] * w[k] = w[k]*(h[k] + 1)である。最初の重みw[0]は常に1であるべきである。そこから始めて、次のような値になります。

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(一般的な関係 w[k-1] = k! は帰納法で簡単に証明されます)。

数列を変換して得られる数は、s[k] * w[k]の和となり、kは0からn-1までとなります。ここで、s[k] は、数列の k 番目 (0 から始まる右端) の要素です。例として、{1, 2, 0, 1, 0}から右端の要素を取り除いたものを考えてみましょう。 {1, 2, 0, 1} . この場合、和は 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 1 * 1 となります。 37 .

すべてのインデックスについて最大の位置を取ると、{4, 3, 2, 1, 0}となり、これは119に変換されることに注意してください。数値のエンコーディングの重みは、どの数値もスキップしないように選択されているので、0 から 119 までのすべての数値が有効です。これは、この例でn=5としたときのn!であり、まさに順列の数と同じです。つまり、エンコードされた数字は、すべての可能な並べ換えを完全に特定していることがわかります。

変数ベースからのデコード

デコードは2進数や10進数への変換に似ています。一般的なアルゴリズムはこうです。

int number = 42;
int base = 2;
int[] bits = new int[n];

for (int k = 0; k < bits.Length; k++)
{
    bits[k] = number % base;
    number = number / base;
}

私たちの変数ベース番号のために。

int n = 5;
int number = 37;

int[] sequence = new int[n - 1];
int base = 2;

for (int k = 0; k < sequence.Length; k++)
{
    sequence[k] = number % base;
    number = number / base;

    base++; // b[k+1] = b[k] + 1
}

これは 37 を {1, 2, 0, 1} に正しくデコードしています ( sequence は {1, 0, 2, 1} となりますが、適切なインデックスを付ければ問題ありません）。元のシーケンス {1, 2, 0, 1, 0} に戻すには、右端に 0 を追加するだけです (最後の要素は常にその新しい位置に対して 1 つしか可能性がないことを覚えておいてください)。

インデックスシーケンスを使用したリストのパーミュテーション

以下のアルゴリズムを使って、特定のインデックスシーケンスに従ったリストの並べ替えができます。これは残念ながらO(n²)アルゴリズムです。

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];

for (int i = 0; i < n; i++)
{
    int s = sequence[i];
    int remainingPosition = 0;
    int index;

    // Find the s'th position in the permuted list that has not been set yet.
    for (index = 0; index < n; index++)
    {
        if (!set[index])
        {
            if (remainingPosition == s)
                break;

            remainingPosition++;
        }
    }

    permuted[index] = list[i];
    set[index] = true;
}

並べ換えの一般的な表現

通常、順列は今回のような直感的でない表現ではなく、単純に順列適用後の各要素の絶対位置で表現します。私たちの例では、{1, 2, 0, 1, 0}を abcde から caebd は通常 {1, 3, 0, 4, 2} で表されます。0から4（または一般的には0からn-1）までの各インデックスは、この表現でちょうど1回出現します。

この形式での並べ換えを適用するのは簡単です。

int[] permutation = new int[] { 1, 3, 0, 4, 2 };

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

for (int i = 0; i < n; i++)
{
    permuted[permutation[i]] = list[i];
}

反転させるとよく似ています。

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

我々の表現から共通の表現への変換

インデックス列を使ってリストを並べ替えるアルゴリズムを、恒等並べ換え {0, 1, 2, ..., n-1} に適用すると、次のようになることに注意してください。 逆順序 という順列が得られますが、これは一般的な形式で表されます。( {2, 0, 4, 1, 3} を例にしています)。

非反転の前置換を得るために、先ほど示した順列アルゴリズムを適用します。

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];

for (int i = 0; i < n; i++)
{
    normal[identity[i]] = list[i];
}

あるいは、逆順列アルゴリズムを使って、順列を直接適用することもできます。

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

int[] inverted = { 2, 0, 4, 1, 3 };

for (int i = 0; i < n; i++)
{
    permuted[i] = list[inverted[i]];
}

一般的な形式の並べ換えを扱うアルゴリズムはすべてO(n)であるのに対し、我々の形式の並べ換えを適用するのはO(n²)であることに注意してください。並べ換えを何度か適用する必要がある場合は、まずそれを共通表現に変換します。