编码系统按数量排序1 [英] Encoding system sorted by the number of 1

问题描述

我认为是编码系统。 arr [（编码代码）] =（解码代码）如下：

I thought an encoding system. arr[(encoded code)]=(decoded code) follows:

• arr 是小于2 ^ 16（pow（2，16））的二进制非负整数数组。

• arr is an array of binary non-negative integers, less than 2^16 (pow(2, 16)).

arr [0] = 0

每个 arr [137 ... 696] 具有三个1。 （111，1011，1101，1110 ...）

each of arr[137...696] has three 1s. (111, 1011, 1101, 1110...)

...每个在 arr [[16C（ n-1））...（（16Cn）的总和）-1] 具有 n 1s。

... each of binary in arr[(sum of 16C(n-1))...(sum of (16Cn))-1] has n 1s.

我没有决定如何在每个部分中进行排序，这并不重要。 （但是，各部分应按数字1进行排序。）合适的编解码算法将决定如何进行排序。 （例如，可以是 arr [1] = 4 ， arr [2] = 2 和 arr [3] = 8 如果算法还不错。）

I didn't decide how to sort in each section, and it doesn't matter. (Sections should be sorted by the number of 1, however.) Suitable encoding-decoding algorithm will decide how to sort. (e.g. It can be arr[1]=4, arr[2]=2 and arr[3]=8 if the algorithm is fine.)

我想制作一个编码功能和解码功能，而无需在此搜索表。任何好的解决方案

I want to make an encoding function and decoding function without searching in this table. Any good solution & sorting method?

推荐答案

让我们将 C（i，j）设为长度为 i 且恰好为 j 1 s。这是众所周知的选择函数，其计算方式为 i！ /（j！*（i-j）！）。

Let's let C(i, j) be the count of binary strings of length i with exactly j 1s. This is the well-known choose function, which is calculated as i! / (j! * (i-j)!).

让我们对它们进行如下排序。首先是 C（16，0）没有 1 的情况。然后 C（16，1）和一个 1 。然后是 C（16，2）和两个 1 ，依此类推。在一组中，我们按字典顺序排序。因此，在 C（16，2）组中，我们将 C（15，2）放在后面的两个 1 s和前导 0 ，然后是 C（15，1），前导 1 和尾随 1 。

Let's sort them as follows. First the C(16, 0) with no 1s. Then the C(16, 1) with one 1. Then the C(16, 2) with two 1s and so on. Within a group we sort lexicographically. Therefore in the C(16, 2) group, we put the C(15, 2) with two trailing 1s and a leading 0, followed by the C(15, 1) with a leading 1 and a trailing 1 somewhere.

现在给定一个二进制字符串，它前面有哪些？ 1 s少于的所有元素都是C（16，0）+ C（16，1）+ ... + C（16 ，i-1）（如果该对象有 i 个）。然后，对于字符串中的每个 1 ，我们知道有多少匹配到该位置，在那里有一个 0 ，其余的 1 之后。这是先前的一组。这些都是先前的，因此加起来就知道了这个位置。对于少于$ 1 s的计数，此计算最多需要16个步骤，并且对于二进制数中的 1 s，最多执行另外的 16 步骤，最多32个步骤。

Now given a binary string, which ones came before it? All of the ones with fewer 1s which is C(16, 0) + C(16, 1) + ... + C(16, i-1) if this one has i ones. And then for each 1 in the string, we know how many match it up to that spot, have a 0 there, and the rest of the 1s later. Which is a group of those previous. And those are all the previous ones so add those up and we know the position that this one goes in. This calculation takes at most 16 steps for the count with fewer 1s and another at most 16 steps for the 1s in the binary number for at most 32 steps.

另一种方式呢？我们首先继续减去 f（16，0）， f（16，1），依此类推，直到我们找出二进制数中必须有多少 1 个。然后，我们从左侧开始，继续计算每个数字是否需要足够的数字，可以放入 1 并减去找到的一组数字，或者这里应该是 0 。同样，这最多需要32个步骤。

What about the other way? We first keep on subtracting of f(16, 0), f(16, 1), and so on until we find out how many 1s must be in the binary number. Then we start at the left and keep figuring out for each digit if we need enough before this one that we can put in a 1 and subtract off a group we found, or whether there should be a 0 here. Again this needs at most 32 steps.

这篇关于编码系统按数量排序1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！