如何对长度为N、2位的字符串进行排序？

Question

我有一个长度为N、2位的字符串。我试图找到一个函数来为这些字符串排序。例如：F(110)=1

F(110) = 1

F(101) = 2

F(011) = 3

我采用的策略是按位的位置来标注，所以对于第一种情况，K=1，L=2，因此是

F(1,2) = 1

F(1,3) = 2

F(2,3) = 3

有谁知道这个函数可能是什么？

Answer 1

如果你处理的是实际的字符串，按字母顺序升序排列。如果你处理的是整数，有一些变通的方法。

• 把整数转换为位串，然后按字母升序排序。

或

• 将整数中的位数反过来 (011 成为 110)并按数字升序排序。

然而，这些变通方法可能很慢。你所描述的函数F被证明是非常简单的（假设给你1-bits的位置），因此是一个很好的解决方案。

为了得出F的实现，我们首先看一下所有正好有两个1-bits的位串的序列。在这里，我们不关心位串的长度。我们只是简单地从左到右递增位串（与通常阿拉伯数字的解释相反，从右到左递增）。

在实际的位串旁边，我将所有的 0 由 .，左边 1 由 l和右边 1 由 r. 这使得它更容易看到模式。

 1:   11       lr
 2:   101      l.r
 3:   011      .lr
 4:   1001     l..r
 5:   0101     .l.r
 6:   0011     ..lr
 7:   10001    l...r
 8:   01001    .l..r
 9:   00101    ..l.r
10:   00011    ...lr
11:   100001   l....r
 …    …        …

函数F应该是计算递增到给定位串所需的步数.在下面，L是左1位的索引，R是右1位的索引。和你的问题一样，我们使用基于1的索引。也就是说，一个字符串中最左边的字符的索引是1。

为了使右边的 1 位向右移动一个位置，左边的 1 位必须" "。追赶". 如果左1位从L=1开始，那么追赶需要R-1步（当把开始步数L=1也算上）。要使右1位达到高位，左1位必须多次追赶，因为右1位每次向右移动1位时，都要回到起点。每次追赶的时间都要长一点，因为右1位离起点更远。第一次需要1步，然后是2步，然后是3步，以此类推。因此，对于右1位到达位置R，需要1+2+3+...+(R-1)步=(R-1)-(R-2)2步。之后，我们只需将左1位移动到其位置，需要L步。因此，函数为

F(L,R) := (R-1)-(R-2) 2 + L。

注意，只有在知道 L 和 R 的情况下，这个函数才容易实现。如果你有一个整数，并且需要先确定 L 和 R，那么反转整数并按数字升序排序可能会更容易和更快。确定 L 和 R 可能比反转整数的位数要慢。