我想到了一个编码系统。arr[(encoded code)]=(decoded code)如下：
arr是小于 2^16 (pow(2, 16)) 的二进制非负整数数组。
arr[0]=0
- each of
arr[1...16]有一个 1。（1、10、100、1000...）
- each of
arr[17...136]有两个 1。 （11、101、110、1001...）
each of arr[137...696]有三个 1。 （111、1011、1101、1110...）
...每个二进制arr[(sum of 16C(n-1))...(sum of (16Cn))-1] has n 1s.
- each of
arr[65519...65534]有十五个 1。
-
arr[65535]是 2^16-1 (1111 1111 1111 1111).
我没有决定每个部分如何排序，这并不重要。 （然而，部分应该按 1 的数量排序。）合适的编码-解码算法将决定如何排序。 （例如，它可以是arr[1]=4, arr[2]=2 and arr[3]=8如果算法没问题的话。）
我想制作一个编码函数和解码函数，而不需要在这个表中搜索。有什么好的解决方案和排序方法吗？
让我们让C(i, j)是长度为二进制字符串的计数i恰好与j 1s。这是众所周知的选择函数，其计算公式为i! / (j! * (i-j)!).
让我们按如下方式对它们进行排序。首先是C(16, 0)没有1s。然后C(16, 1)与一个1。然后C(16, 2)有两个1等。在一个组中，我们按字典顺序排序。因此在C(16, 2)组，我们把C(15, 2)有两个尾随1s 和一个领先的0，随后是C(15, 1)具有领先的1和一个尾随的1某处。
现在给定一个二进制字符串，哪些在它之前？所有数量较少的1s 这是C(16, 0) + C(16, 1) + ... + C(16, i-1)如果这个有i那些。然后对于每个1在字符串中，我们知道有多少个与该位置匹配，有一个0那里，以及其余的1稍后。这是以前的一组。这些都是前面的，所以把它们加起来，我们就知道了这个的位置。这个计算最多需要 16 步来计算更少的数1最多 s 和另一个16步骤为1s 的二进制数最多为 32 步。
那另一种方式呢？我们首先继续减去f(16, 0), f(16, 1)，依此类推，直到我们找出有多少个1s 必须是二进制数。然后我们从左边开始，继续计算每一位数字，如果我们在这之前需要足够的数字，我们可以在其中放入一个1并减去我们找到的一组，或者是否应该有一个0这里。同样，这最多需要 32 个步骤。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
