求特征属性的第k个二进制数的算法

Question

假设我们将考虑具有长度2n且n可能是大约的二进制数1000.我们正在寻找具有以下特性的kth数字(k受限制10^9):

• 金额1's等于0's可以描述如下的金额:#(1) = #(0)
• 这个数字的每个前缀都有到ATLEAST包含尽可能多0's的1's.在否定句子后可能更容易理解它,即:没有包含1's多于的前缀0's.

基本上就是这样.所以为了说清楚,让我们做一些例子: n=2,k=2 我们必须采用二进制数量的长度2n:

0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...

现在我们必须找到2nd满足这两个要求的数字.所以我们看到的0011是第一个,0101也是第二个.如果我们改变k=3,则答案不存在,因为存在具有相同数量的相反位的数字,但是因为0110存在前缀,011所以数字不满足第二约束,并且对于具有1最高有效位的所有数字也是如此.

那么我到目前为止所做的算法呢？

好吧,我的第一个想法是生成所有可能的位设置,并检查它是否具有这两个属性,但生成它们都将采用O(2^(2n))哪个不是一个选项n=1000.

另外我意识到没有必要检查所有小于0011for n=2,000111for n=3等的数字......坦率地说,那些最重要位的一半仍保持"未被触及",因为这些数字不可能满足#(1) = #(0)条件.使用它我可以减少n一半,但它没有多大帮助.而不是2*永远我有永远运行算法.它仍然很O(2^n)复杂,太大了.

算法的任何想法？

结论

这篇文章是在读完安迪·琼斯的帖子之后根据我的想法创建的.

首先,我不会发布我使用过的代码,因为它是Andy发布2009年Kasa之后的第6点.你所要做的就是考虑nr我所描述的那样k.取消Dyck单词算法,可以帮助我们更快地找到答案.但它有一个瓶颈.

while (k >= C(n-i,j))

考虑到这一点n <= 1000,加泰罗尼亚的数字可能非常大,甚至C(999,999).我们可以使用一些大数字算术,但另一方面,我想出了一个小技巧来绕过它并使用标准整数.

我们不想知道加泰罗尼亚数字实际上有多大,只要它大于k.所以现在我们将在n x n表格中创建缓存部分和的加泰罗尼亚数字.

...                                     ...
5 |                              42     ...
4 |                        14    42     ...
3 |                   5    14    28     ...
2 |             2     5     9    14     ...
1 |       1     2     3     4     5     ...
0 | 1     1     1     1     1     1     ...
   ----------------------------------   ...
    0     1     2     3     4     5     ...

生成它是非常简单的:

C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x
C(x,y) = C(x,y-1) where x == y

所以我们只能看到这个:

C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x

会导致溢出.

让我们停在这一点并提供定义.

k-flow- 它不是整数的实际溢出,而是值C(x,y)大于的信息k.

我的想法是在每次运行上面的公式后检查是否C(x,y)比k任何和组件更重要-1.如果是这样的话,我们会把-1它作为一个标记,而这k-flow已经发生了.我猜很明显,如果k-flow数字与任何正数相加,那么它仍然k-flowed特别是2 k-flowed个数的总和k-flowed.

我们要证明的最后一点是,不可能创造真正的溢出.真正的溢出可能只发生在我们总结a + b它们中的哪一个而不是k-flowed它们产生真正溢出的总和时.

当然,这是不可能的,因为最大值可以描述为a + b <= 2 * k <= 2*10^9 <= 2,147,483,647这个不等式中的最后一个值是符号int的值.我还假设int有32位,就像我的情况一样.

Answer 1

您描述的数字对应于戴克的话。Kasa 2009的第 2 部分给出了一个简单的算法，用于按字典顺序枚举它们。如果您想进一步阅读，它的参考资料应该会有所帮助。

顺便说一句（请注意，我写这篇文章时我正在半睡半醒，所以它可能是错误的），维基百科文章指出，戴克长度的单词数2n是n加泰罗尼亚语数字C(n)。您可能想要找到n比您要查找的C(n)更大的最小单词k，然后枚举从 开始的 Dyck 单词X^n Y^n。