迭代洗牌[0..N），而不阵列

Question

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

X _{n + 1个} =例程（X _Ñ，最大值）

例如，像一个LCG发生器：

X _{N + 1} =（A * X _n + c）mod m

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

梦功能：

X _{n + 1个} =例程（X _Ñ，最大，置换数）

此例程，由索引参数到集中的所有的排列，将返回序列中的下一个数字。该序列可能是任意大的（因此存储阵列和使用事实数字是不切实际的。）

失败的是，有没有人有类似的功能指针，无论是无状态的还是具有恒定量的状态为任意'max'，例如他们会迭代一个洗牌列表

Answer 1

是否有可能索引一组排列而不预先计算并将所有内容存储在内存中？我之前尝试过类似的方法，但没有找到解决方案 - 我认为它是不可能（在数学意义上）

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

Answer 2

从我的回应another question：

它实际上是可能的 空间成正比，这样做是为了 元素的选择的号码，而不是设定的 大小，你是从， 不管选择您选择的全部集合的比例为 。这样做 这通过产生一个随机 置换，然后从中选择 这样的：

选择一个块密码，诸如TEA 或XTEA。使用XOR folding至 将块大小减小为最小的 ，其功率比您选择的集合 大。使用随机的 种子作为密码的关键。至 生成 排列中的元素n，使用 加密对n进行加密。如果输出号码不在 您的设置中，请将其加密。重复，直到 数字在集合内。在 平均你将不得不做每个生成的数字两次加密少于 。 这有一个额外的好处，如果 你的种子密码安全， 所以你的整个排列。

我在这方面写得更详细了 here。

当然，还有每一个排列可产生不能保证（并根据您的块大小和密钥大小，可能甚至是不可能的），但你可以得到的排列是高度随机的（如果他们间没有这不会是一个好的密码），并且你可以拥有尽可能多的密码。

Answer 3

如果你想要一个占用较少堆栈空间的函数，那么你应该考虑使用迭代版本，而不是函数。您也可以像TreeMap一样使用数据结构，并将其存储在磁盘上，并根据需要进行阅读。

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

Answer 4

还有n！ n个元素的排列。存储你正在使用哪一个需要至少log（n！）/ log（2）位。通过斯特林近似，这大约需要log（n）/ log（2）位。

显式存储一个索引需要log（n）/ log（2）位。存储所有的n，就像在一个索引数组中一样多n次，或者再次n log（n）/ log（2）。信息理论上，没有比明确存储排列更好的方法。

换句话说，您要传递的集合中的排列的索引采用相同的渐近存储空间，就像写出排列一样。例如，如果您将排列的索引限制为32位值，则只能处理多达12个元素的排列。 64位索引只能让你达到20个元素。

由于指数采取相同的空间置换会，要么改变你的表现，只是直接使用置换或接受解包成大小N的数组解包置换索引到一个数组

Answer 5

代码，从索引到排列有一定的映射。有很多其他人，但这个很方便。

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

Answer 6

使用迭代接口的代码。时间复杂度为O（n^2），空间复杂度的开销是：复制n（log n bits），迭代变量（log n bits），跟踪ni（log n bits），复制当前值（记录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); 
    } 
}