我知道几个例程的工作方式如下：

Xn+1 = Routine(Xn, max)

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

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

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

梦功能：

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

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

失败的话，是否有人指向类似的函数，这些指针或者是无状态的，或者具有针对任意" max"的恒定数量的状态，这样它们将迭代经过重排的列表。

解决方案

是否可以索引一组排列而无需事先计算并将整个对象存储在内存中？我以前尝试过类似的方法，但没有找到解决方案，我认为这是不可能的(从数学意义上来说)。

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

根据我对另一个问题的回答：

It is actually possible to do this in
  space proportional to the number of
  elements selected, rather than the
  size of the set you're selecting from,
  regardless of what proportion of the
  total set you're selecting. You do
  this by generating a random
  permutation, then selecting from it
  like this:
  
  Pick a block cipher, such as TEA
  or XTEA. Use XOR folding to
  reduce the block size to the smallest
  power of two larger than the set
  you're selecting from. Use the random
  seed as the key to the cipher. To
  generate an element n in the
  permutation, encrypt n with the
  cipher. If the output number is not in
  your set, encrypt that. Repeat until
  the number is inside the set. On
  average you will have to do less than
  two encryptions per generated number.
  This has the added benefit that if
  your seed is cryptographically secure,
  so is your entire permutation.
  
  I wrote about this in much more detail
  here.

当然，不能保证可以生成每个排列(并且取决于块大小和键大小，甚至可能无法生成)，但是我们可以获得的排列是高度随机的(如果不是，则不会)。成为一个很好的密码)，我们可以根据需要拥有任意数量的密码。

如果要使用占用较少堆栈空间的函数，则应考虑使用迭代版本，而不是函数。我们还可以使用像TreeMap这样的数据结构，并将其存储在磁盘上，并根据需要进行读取。

X(n+1) = Routine(Xn, max, permutation number)
for(i = n; i > 0; i--)
 {
   int temp = Map.lookup(i) 
   otherfun(temp,max,perm)
 }

有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的数组。

将排列索引分解为数组的代码，并具有从索引到排列的特定映射。有很多其他的东西，但是这很方便。

#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);
}

使用迭代接口的代码。时间复杂度为O(n ^ 2)，空间复杂度的开销为：复制n(日志n位)，迭代变量(日志n位)，跟踪ni(日志n位)， (对数n位)，p的副本(n对数n位)，创建下一个值(对数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);
    }
}