具有某些性质的第k个二进制数的算法

Question

假设我们将考虑长度为2n且n的二进制数可能约为1000。我们正在寻找具有以下特性的kth编号（k受10^9限制）：

• 1的量等于0的量，可以描述如下：#（1）=#（0）
• 这个数字的每个前缀都必须至少包含与0的和1的一样多的0的。否定句子后可能更容易理解，即：没有前缀会包含比0的更多的1的。

基本上就是这样。为了清楚起见，让我们做一些例子：n=2，k=2我们必须取长度2n的二进制数：

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

现在我们必须找到满足这两个要求的第二个编号。所以我们看到0011是第一个，而0101是第二个。如果我们改变k=3，那么答案就不存在了，因为有一些数字具有相同数量的相反位，但是对于0110，有前缀011，所以这个数字不满足第二个约束，所有以1作为最高有效位的数字都是一样的。

那么到目前为止我是怎么找到算法的呢？

我的第一个想法是生成所有可能的位设置，并检查它是否具有这两个属性，但生成它们都需要O（2^（2n）），这不是n=1000的选项。

此外，我意识到没有必要检查所有小于0011的数字是否为n=2，000111是否为n=3，等等。。。坦率地说，那些最高有效位的一半保持“未触及”，因为这些数字不可能满足#（1）=#（0）条件。使用它，我可以将n减少一半，但没有多大帮助。我用的是永远运行的算法，而不是2*forever。它仍然是O（2^n）复杂性，这太大了。

对算法有什么想法吗？

结论

这篇文章是我读了安迪·琼斯的帖子后思考的结果。

首先，我不会发布我使用过的代码，因为这是安迪2009年发布的帖子中的第6点。你所要做的就是把nr看作我所说的k。解开Dyck单词算法，将帮助我们更快地找到答案。然而，它有一个瓶颈。

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

考虑到n

我们不想知道加泰罗尼亚数字到底有多大，只要它大于k。现在我们将在nxn表中创建加泰罗尼亚数字缓存部分和。

...                                     ...
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，特别是2k-flowed数之和是k-flowed。

最后，我们要证明的是，不可能造成真正的溢出。只有当我们将ab中的哪一个不是k-flowed求和时，才可能发生真正的溢出，但作为和，它们产生了真正的溢出。

当然这是不可能的，因为最大值可以描述为a b




Answer 1

很抱歉上次我误解了这个问题，所以我编辑了它，现在我可以保证更正，你可以先测试代码，复杂性是O（n^2），详细答案如下

首先我们可以把这个问题等同于下一个问题

我们正在寻找具有以下属性的第k个最大数（k受10^9的限制）：

• 1的量等于0的量，可以描述如下：#（1）=#（0）
• 这个数字的每个前缀必须至少包含与0的一样多的[[1的]]，这意味着：没有前缀会包含更多的[[0的比1的]]。

让我们举一个例子来解释它：让n=3和k=4，满足的数字量是5，下面的图片解释了我们应该在以前的问题和新问题中确定什么：

|                       000111  ------>    111000                          ^
|                       001011  ------>    110100                          |
|                       001101  ------>    110010                          |
|  previous 4th number  010011  ------>    101100  new 4th largest number  |
v                       010101  ------>    101010                          |

所以在我们解决了这个新问题之后，我们只需要按位而不是。

现在主要的问题是如何解决新问题。首先，让A是数组，所以A[m]{1

A[1]只能是1或0，如果A[1]=1，数字的数量是DP[2n-1][n-1]，如果A[1]=0，数字的数量是DP[2n-1][n]，现在我们想找到第k个最大的

（我们使用动态规划确定DP矩阵，DP方程为DP[v][q]=DP[v-1][q-1]DP[v-1][q]）

   Intention: we need the number in leftest row can be compared,
              so we add a row on DP's left row, but it's not include by DP matrix
              in the row, all the number is 1.
              the number include by bracket are initialized by ourselves
              the theory of initialize just follow the mean of DP matrix

   DP matrix = (1) (0) (0) (0)                4<=DP[5][2]=5  -->  A[1]=1
               (1) (1) (0) (0)                4>DP[4][1]=3  -->  A[2]=0, k=4-3=1
               (1) (2) (0) (0)                1<=DP[3][1]=3  -->  A[3]=1
               (1) (3)  2  (0)                1<=1  -->  a[4]=1
               (1) (4)  5  (0)                no number to compare, A[5]~A[6]=0
               (1) (5)  9   5                 so the number is 101100

如果你还不明白，你可以用代码来理解

意图：DP[2n][n]增长非常快，所以代码只有在n时才能工作

/*-------------------------------------------------- 
    Environment: X86 Ubuntu GCC 
    Author: Cong Yu 
    Blog: aimager.com                              
    Mail: [e-mail]                      
    Build_Date: Mon Dec 16 21:52:49 CST 2013 
    Function: 
--------------------------------------------------*/

#include <stdio.h>

int DP[2000][1000];
// kth is the result
int kth[1000];

void Oper(int n, int k){
    int i,j,h;
    // temp is the compare number
    // jishu is the 
    int temp,jishu=0;

    // initialize
    for(i=1;i<=2*n;i++)
        DP[i-1][0]=i-1;
    for(j=2;j<=n;j++)
        for(i=1;i<=2*j-1;i++)
            DP[i-1][j-1]=0;
    for(i=1;i<=2*n;i++)
        kth[i-1]=0;

    // operate DP matrix with dynamic programming
    for(j=2;j<=n;j++)
        for(i=2*j;i<=2*n;i++)
            DP[i-1][j-1]=DP[i-2][j-2]+DP[i-2][j-1];

    // the main thought
    if(k>DP[2*n-1][n-1])
        printf("nothing\n");
    else{
        i=2*n;
        j=n;
        for(;j>=1;i--,jishu++){
            if(j==1)
                temp=1;
            else
                temp=DP[i-2][j-2];

            if(k<=temp){
                kth[jishu]=1;
                j--;
            }
            else{
                kth[jishu]=0;
                if(j==1)
                    k-=1;
                else
                    k-=DP[i-2][j-2];
            }
        }
        for(i=1;i<=2*n;i++){
            kth[i-1]=1-kth[i-1];
            printf("%d",kth[i-1]);
        }
        printf("\n");
    }
}

int main(){
    int n,k;
    scanf("%d",&n);
    scanf("%d",&k);
    Oper(n,k);
    return 0;
}

Answer 2

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

顺便说一句（请注意，我在写这篇文章的时候半睡半醒，所以它可能是错误的），维基百科的文章指出，长度2n的Dyck单词数是nth Catalan number，C（n）。您可能希望找到最小的n，以便C（n）大于您要查找的k，然后枚举从X^n Y^n开始的Dyck单词。