位和字节：存储洗牌指令

Question

给定一个长度为 2 的字节数组，我们有两种洗牌的可能性。 01 和 10

长度为 3 将允许这些随机播放选项 012、021、102代码>、<代码>120、<代码>102、<代码>201、<代码>210。总共 2x3=6 个选项。

长度为 4 将有 6x4=24。长度为 5 将有 24x5=120 个选项，等等。

因此，一旦您随机选择了这些随机选项之一，您如何存储它？您可以存储 23105 来指示如何打乱四个字节。但这需要 5x3=15 位。我知道它可以用 7 位完成，因为只有 120 种可能性。

有什么想法如何更有效地存储洗牌指令吗？它应该是一个可以扩展长度的算法。

编辑：在发布之前请参阅下面的我自己的答案一个新的。我确信许多已经存在的答案中都有很好的信息，但我只是无法理解其中的大部分内容。

Answer 1

如果您对要打乱的元素集有良好排序，那么您可以为所有排列的集合创建一个良好排序，并仅存储一个表示排列在顺序中的位置的整数。

例子：
打乱1 4 5：可能性是：

1 4 5   [0]
1 5 4   [1]
4 1 5   [2]
4 5 1   [3]
5 1 4   [4]
5 4 1   [5]

要存储排列415，您只需存储2（零索引）。

如果您对原始元素集有良好的排序，则可以通过从最左边的元素从最小顺序到最大顺序迭代元素，同时迭代下一个元素的剩余元素来对排列集进行良好排序。向右放置，依此类推，直到到达最右边的元素。您不需要存储这个数组，您只需要能够再次以相同的顺序生成排列以“解包”存储的整数。

然而，尝试一一生成所有排列将花费超出最小集合的相当多的时间。您可以观察到第一个 (N-1)! 排列从第一个元素开始，第二个 (N-1)! 排列从第二个元素开始，然后，对于以特定元素开头的每个排列，第一个 (N-2)! 排列从第一个剩余元素开始，依此类推。这将允许您“打包”或“解包”O(n) 中的元素，但实际生成阶乘以及任意长度整数的除法和模数的复杂性除外，这将是相当大的。

Answer 2

您是对的，要仅存储数据的排列，而不是数据本身，您只需要 ceil(log2(permutations)) 那么多的位。对于 N 个项目，排列的数量为阶乘 (N) 或 N!，因此您需要 ceil(log2(factorial(N))) 位来仅存储 N 个项目的排列，而不存储项目。

无论您熟悉哪种语言，都应该有一种现成的方法来制作一个 M 位的大数组，用排列填充它，然后将其存储在存储设备上。

Answer 3

一种常见的洗牌算法，也是少数无偏的算法之一，是 Fisher-Yates 洗牌。该算法的每次迭代都会采用一个随机数，并根据该数字交换两个位置。通过存储这些随机数的列表，您可以稍后重现完全相同的排列。

此外，由于每个数字的有效范围都是预先知道的，因此您可以通过将每个数字乘以较低数字的有效范围的乘积将它们全部打包成一个大整数，就像一种可变基数位置表示法。

Answer 4

对于 L 个项目的数组，为什么不将顺序打包到 L*ceil(log2(L)) 位中？ （ceil(log2(L)) 是保存 L 个唯一值所需的位数）。 例如，以下是“未洗牌”洗牌的表示，按顺序取出项目

L=2:  0 1       (2 bits)
L=3:  00 01 10     (6 bits)
L=4:  00 01 10 11   (8 bits)
L=5:  000 001 010 011 100 (15 bits)
...
L=8:  000 001 010 011 100 101 110 111 (24 bits)
L=9:  0000 0001 0010 0011 0100 0101 0110 0111 1000 (36 bits)
...
L=16: 0000 0001 ... 1111  (64 bits)
L=128: 00000000 000000001 ... 11111111 (1024 bits)

：与@user470379的答案相比，该方案的优点是提取索引非常容易，只需移位和掩码即可。无需重新生成排列表。这对于大 L 来说应该是一个巨大的胜利：（对于 128 个项目，有 128！= 3.8562e+215 种可能的排列）。

（排列 == “可能性”；阶乘 = L!= L * (L-1) * ... * 1 = 正是您计算可能性的方式）

方法也不比存储排列索引大多少。您可以将 128 个项目随机存储在 1024 位（32 x 32 位整数）中。存储 128! 需要 717 位（23 个整数）。

考虑到更快的解码速度和计算排列不需要临时存储的事实，存储额外的 9 个整数可能是非常值得的。

---

这是 Ruby 中的一个实现，它应该适用于任意大小。 “随机播放指令”包含在数组指令中。第一部分使用@Theran提到的Fisher-Yates算法的版本来计算洗牌

# Some Setup and utilities
sizeofInt = 32  # fix for your language/platform
N = 16
BitsPerIndex = Math.log2(N).ceil
IdsPerWord = sizeofInt/BitsPerIndex

# sets the n'th bitfield in array a to v
def setBitfield a,n,v
  mask = (2**BitsPerIndex)-1
  idx = n/IdsPerWord
  shift = (n-idx*IdsPerWord)*BitsPerIndex
  a[idx]&=~(mask<<shift)
  a[idx]|=(v&mask)<<shift
end

# returns the n'th bitfield in array a
def getBitfield a,n
  mask = (2**BitsPerIndex)-1
  idx = n/IdsPerWord
  shift = (n-idx*IdsPerWord)*BitsPerIndex
  return (a[idx]>>shift)&mask
end  

#create the shuffle instruction in linear time 
nwords = (N.to_f/IdsPerWord).ceil  # num words required to hold instruction
instruction = Array.new(nwords){0} # array initialized to 0

#the "inside-out" Fisher–Yates shuffle
for i in (1..N-1)
  j = rand(i+1)
  setBitfield(instruction,i,getBitfield(instruction,j))
  setBitfield(instruction,j,i)
end

#Here is a way to visualize the shuffle order
#delete ".reverse.map{|s|s.to_i(2)}" to visualize the way it's really stored
p instruction.map{|v|v.to_s(2).rjust(BitsPerIndex*IdsPerWord,'0').scan(
    Regexp.new('.'*BitsPerIndex)).reverse.map{|s|s.to_i(2)}}

。这是将洗牌应用于字符数组的示例：

A=(0...N).map{|v|('A'.ord+v).chr}
puts A*''

#Apply the shuffle to A in linear time
for i in (0...N)
 print A[getBitfield(instruction,i)]
end
print "\n"

#example: for N=20, produces
> ABCDEFGHIJKLMNOPQRST
> MSNOLGRQCTHDEPIAJFKB

希望这不会太难转换为javascript或任何其他语言。

Answer 5

如果之前的答案已经涵盖了这一点，我很抱歉，但这是第一次，这些答案对我来说完全陌生。我可能会提到，我了解 Java 和 JavaScript，但我对数学一无所知……所以 log2、排列、factorial、well-ordering 对我来说都是陌生的词。

最重要的是，我最终（再次）使用 StackOverflow 作为白板来写下我的问题，并在 20 分钟后回答了我脑海中的问题。我陷入了与计算机无关的生活中，而且，在了解 StackOverflow 后，我发现现在要节省每个人容易浪费的 20% 以上的时间已经太晚了。

无论如何，迷失在所有三个现有答案中。这是我知道的答案

（用 Javascript 编写，但应该很容易将 20 行外国代码翻译成您选择的语言）

（在此处查看它的实际操作：http://jsfiddle.net/M3vHC)

编辑： 感谢 AShelly 的捕捉：这将失败（变得高度有偏差）当给定的密钥长度超过 12 时，假设您的整数是 32 位（如果您的整数是 64 位，则超过 19）

var keyLength = 5
var possibilities = 1
for(var i = 0; i < keyLength ; i++)
    possibilities *= i+1 // Calculate the number of possibilities to create an unbiased key
var randomKey = parseInt(Math.random()*possibilities) // Your shuffle instruction. Random number with correct number of possibilities starting with zero as the first possibility
var keyArray = new Array(keyLength) // This will contain the new locations of existing indexes. [0,1,2,3,4] means no shuffle [4,3,2,1,0] means reverse order. etcetera
var remainsOfKey = randomKey // Our "working" key. This is disposible / single use.
var taken = new Array(keyLength) // Tells if an index has already been accounted for in the keyArray
for(var i = keyArray.length;i > 0;i--) { // The number of possibilities for the first item in the key array is the number of blanks in key array.
    var add = remainsOfKey % i + 1, remainsOfKey = parseInt(randomKey / i) // Grab a number at least zero and less then the number of blanks in the keyArray
    for(var j = 0; add; j++) // If we got x from the above line, make sure x is not already taken
        if(!taken[j])
            add--
    taken[keyArray[i-1] = --j] = true // Take what we have because it is right
}
alert('Based on a key length of ' + keyLength + ' and a random key of ' + randomKey + ' the new indexes are ... ' + keyArray.join(',') + ' !')