迭代洗牌[0到n），而阵列 [英] Iterating shuffled [0..n) without arrays

问题描述

我认识一对夫妇的例程的工作方式如下：

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

X <子> N + 1 =例程（X <子> N ，最大值）

X_n+1 = Routine(X_n, max)

例如，像一个LCG发电机：

For example, something like a LCG generator:

X <子> N + 1 =（A * X <子> N + C）模m

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

没有足够的参数在这个发生器，以产生每一个序列。

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

梦幻功能：

X <子> N + 1 =例程（X <子> N ，最大值，置换数）

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

此例程，由索引参数到该组的所有排列的，将返回序列中的下一个号码。该序列可以是任意大（这样存储阵列和使用factoradic号码是不切实际的。

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.

推荐答案

有N！ n个元素的排列。你使用哪一个存储至少需要数（N！）/日志（2）位。通过斯特灵公式，这需要大约N日志（N）/日志（2）位。

There are n! permutations of n elements. Storing which one you're using requires at least log(n!) / log(2) bits. By Stirling's approximation, this takes roughly n log(n) / log (2) bits.

明确地存储一个索引需要的log（n）/日志（2）位。存储所有的n，在指数数组需要n倍之多，或者再次N日志（N）/日志（2）。理论上信息，没有比明确地​​存储置换更好的方法。

Explicitly storing one index takes log(n) / log(2) bits. Storing all n, as in an array of indices takes n times as many, or again n log(n) / log(2). Information-theoretically, there is no better way than explicitly storing the permutation.

在换句话说，指数你传递什么样排列在你想要的设置采用相同的渐近的存储空间，只是写了置换。如果，因为，例如，你限制了置换的指数为32位值，你只能处理高达12个元素的排列。 64位指数只给你达20元素。

In other words, the index you pass in of what permutation in the set you want takes the same asymptotic storage space as just writing out the permutation. If, for, example, you limit the index of the permutation to 32 bit values, you can only handle permutations of up to 12 elements. 64 bit indices only get you up to 20 elements.

由于指数采用相同的空间置换会，要么改变你再presentation只是直接使用置换或接受解压缩到大小为N的数组。

As the index takes the same space as the permutation would, either change your representation to just use the permutation directly, or accept unpacking into an array of size N.

这篇关于迭代洗牌[0到n），而阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！