8

I know of a couple of routines that work as follows:

Xn+1 = Routine(Xn, max)

For example, something like a LCG generator:

Xn+1 = (a*Xn + c) mod m

There isn't enough parameterization in this generator to generate every sequence.

Dream Function:

Xn+1 = Routine(Xn, max, permutation number)

This routine, parameterized by an index into the set of all permutations, would return the next number in the sequence. The sequence may be arbitrarily large (so storing the array and using factoradic numbers is impractical.

Failing that, does anyone have pointers to similar functions that are either stateless or have a constant amount of state for arbitrary 'max', such that they will iterate a shuffled list.

4

6 に答える 6

4

あります！n 要素の順列。使用しているものを保存するには、少なくとも log(n!) / log(2) ビットが必要です。スターリングの近似により、これにはおおよそ n log(n) / log (2) ビットかかります。

1 つのインデックスを明示的に格納するには、log(n) / log(2) ビットが必要です。インデックスの配列のように、n 個すべてを格納するには、n 倍、つまり n log(n) / log(2) かかります。情報理論的には、順列を明示的に格納するよりも良い方法はありません。

言い換えると、セット内のどの順列を渡すかのインデックスは、順列を書き出すのと同じ漸近的なストレージ スペースを使用します。たとえば、順列のインデックスを 32 ビット値に制限した場合、最大 12 要素の順列しか処理できません。64 ビットのインデックスでは、最大 20 個の要素しか取得できません。

インデックスは順列と同じスペースを取るため、表現を変更して順列を直接使用するか、サイズ N の配列へのアンパックを受け入れます。

于 2008-10-02T23:19:28.177 に答える
3

別の質問に対する私の回答から：

実際には、選択しているセット全体の割合に関係なく、選択しているセットのサイズではなく、選択した要素の数に比例するスペースでこれを行うことができます。これを行うには、ランダムな順列を生成してから、次のように選択します。

TEA や XTEAなどのブロック暗号を選択します。XOR フォールディングを使用して、選択しているセットよりも大きい最小の 2 の累乗にブロック サイズを縮小します。ランダム シードを暗号の鍵として使用します。置換で要素 n を生成するには、n を暗号で暗号化します。出力番号がセットにない場合は、それを暗号化します。数がセット内に収まるまで繰り返します。平均して、生成された数値ごとに 2 回未満の暗号化を行う必要があります。これには、シードが暗号的に安全であれば、順列全体も安全であるという追加の利点があります。

これについては、こちらで詳しく説明 しています。

もちろん、すべての順列が生成されるという保証はありません (また、ブロック サイズとキー サイズによっては、それが不可能な場合もあります)。ただし、取得できる順列は非常にランダムです (そうでない場合は、 t は適切な暗号である必要があります)、必要に応じていくつでも使用できます。

于 2008-10-02T16:07:21.790 に答える
1

占有するスタック スペースが少ない関数が必要な場合は、関数ではなく反復バージョンの使用を検討する必要があります。TreeMap のようなデータ構造を使用して、ディスクに保存し、必要に応じて読み取ることもできます。

X(n+1) = Routine(Xn, max, permutation number)
for(i = n; i > 0; i--)
 {
   int temp = Map.lookup(i) 
   otherfun(temp,max,perm)
 }
于 2008-10-02T16:26:32.787 に答える
0

Is it possible to index a set of permutations without previously computing and storing the whole thing in memory? I tried something like this before and didn't find a solution - I think it is impossible (in the mathematical sense).

Disclaimer: I may have misunderstood your question...

于 2008-10-02T14:37:37.013 に答える
0

インデックスから順列への特定のマッピングを使用して、順列インデックスを配列にアンパックするコード。他にもたくさんありますが、これは便利です。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char index_t;
typedef unsigned int permutation;

static void permutation_to_array(index_t *indices, index_t n, permutation p)
{
    index_t used = 0;
    for (index_t i = 0; i < n; ++i) {
        index_t left = n - i;
        index_t digit = p % left;
        for (index_t j = 0; j <= digit; ++j) {
            if (used & (1 << j)) {
                digit++;
            }
        }
        used |= (1 << digit);
        indices[i] = digit;
        p /= left;
    }
}

static void dump_array(index_t *indices, index_t n)
{
    fputs("[", stdout);
    for (index_t i = 0; i < n; ++i) {
        printf("%d", indices[i]);
        if (i != n - 1) {
            fputs(", ", stdout);
        }
    }
    puts("]");
}

static int factorial(int n)
{
    int prod = 1;
    for (int i = 1; i <= n; ++i) {
        prod *= i;
    }
    return prod;
}

int main(int argc, char **argv)
{
    const index_t n = 4;
    const permutation max = factorial(n);
    index_t *indices = malloc(n * sizeof (*indices));
    for (permutation p = 0; p < max; ++p) {
        permutation_to_array(indices, n, p);
        dump_array(indices, n);
    }
    free(indices);
}
于 2008-10-03T09:03:51.330 に答える
0

反復インターフェイスを使用するコード。時間計算量は O(n^2)、空間計算量には次のオーバーヘッドがあります: n のコピー (log n ビット)、反復変数 (log n ビット)、ni の追跡 (log n ビット)、現在の値のコピー(log n ビット)、p のコピー (n log n ビット)、次の値の作成 (log n ビット)、および使用される値のビット セット (n ビット)。n log n ビットのオーバーヘッドを回避することはできません。時間的に、これはビットを設定するための O(n^2) でもあります。これは少し減らすことができますが、使用された値を格納するために装飾されたツリーを使用するという犠牲が伴います。

これは、代わりに適切なライブラリへの呼び出しを使用することで、任意精度の整数とビット セットを使用するように変更できます。また、上記の境界は、移植可能に N=8 に制限されるのではなく、実際に開始されます (int は、短く、16 ビットと小さい)。9！= 362880 > 65536 = 2^16

#include <math.h>
#include <stdio.h>

typedef signed char index_t;
typedef unsigned int permutation;

static index_t permutation_next(index_t n, permutation p, index_t value)
{
    permutation used = 0;
    for (index_t i = 0; i < n; ++i) {
        index_t left = n - i;
        index_t digit = p % left;
        p /= left;
        for (index_t j = 0; j <= digit; ++j) {
            if (used & (1 << j)) {
                digit++;
            }
        }
        used |= (1 << digit);
        if (value == -1) {
            return digit;
        }
        if (value == digit) {
            value = -1;
        }
    }
    /* value not found */
    return -1;
}

static void dump_permutation(index_t n, permutation p)
{
    index_t value = -1;
    fputs("[", stdout);
    value = permutation_next(n, p, value);
    while (value != -1) {
        printf("%d", value);
        value = permutation_next(n, p, value);
        if (value != -1) {
            fputs(", ", stdout);
        }
    }
    puts("]");
}

static int factorial(int n)
{
    int prod = 1;
    for (int i = 1; i <= n; ++i) {
        prod *= i;
    }
    return prod;
}

int main(int argc, char **argv)
{
    const index_t n = 4;
    const permutation max = factorial(n);
    for (permutation p = 0; p < max; ++p) {
        dump_permutation(n, p);
    }
}
于 2008-10-03T09:11:36.413 に答える