8

我知道一些如下工作的例程：

X n+1 = 例程（X n , 最大值）

例如，类似 LCG 生成器的东西：

X n+1 = (a*X n + c) mod m

此生成器中没有足够的参数化来生成每个序列。

梦想功能：

X n+1 = 例程(X n , max, 排列数)

该例程通过索引参数化到所有排列的集合中，将返回序列中的下一个数字。序列可能任意大（因此存储数组和使用阶乘数是不切实际的。

如果做不到这一点，是否有人拥有指向类似函数的指针，这些函数要么是无状态的，要么具有任意“最大值”的恒定状态量，这样他们就可以迭代一个混洗列表。

4

6 回答 6

4

有n！n 个元素的排列。存储您正在使用的至少需要 log(n!) / log(2) 位。根据斯特林的近似，这大约需要 n log(n) / log (2) 位。

显式存储一个索引需要 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。如果输出编号不在您的集合中，请对其进行加密。重复直到数字在集合内。平均而言，每个生成的数字必须执行少于两次的加密。这有一个额外的好处，如果你的种子是加密安全的，那么你的整个排列也是如此。

我在这里更详细地写了这个 。

当然，不能保证可以生成每个排列（并且取决于您的块大小和密钥大小，这甚至可能是不可能的），但是您可以获得的排列是高度随机的（如果不是，它不会' t 是一个好的密码），你可以拥有任意数量的密码。

于 2008-10-02T16:07:21.790 回答
1

If you are wanting a function that takes up less stack space, then you should look into using an iterated version, rather than a function. You can also use a datastructure like a TreeMap, and have it stored on disk, and read on an as needed basis.

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

是否可以在不预先计算并将整个事物存储在内存中的情况下索引一组排列？我之前尝试过这样的事情并没有找到解决方案 - 我认为这是不可能的（在数学意义上）。

免责声明：我可能误解了你的问题......

于 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 回答