logo标签列表

寻找具有特定属性的第k个二进制数的算法

algorithmbinarysequencecatalan
9
假设我们考虑长度为2n的二进制数，其中n可能约为1000。我们正在寻找具有以下特性的第k个数字（k受到10^9的限制）：
  • 1的数量等于0的数量，可以描述为：#(1) = #(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倍的永远。它仍然具有O(2^n)复杂度，这太大了。

有任何算法的想法吗？

结论

这篇文章是在阅读安迪·琼斯（Andy Jones）的帖子后思考后产生的结果。

首先，我不会发布我使用的代码，因为这是来自安迪帖子Kasa 2009中的第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位，就像在我的情况下一样。
我没有完整的解决方案，但是经过一番思考，我觉得你可以通过从右边开始决定放置1的位置，并且有一个规则，即只有在那里已经有足够数量的1时才能放置0来构建这样的字符串。例如，如果你有???101，你已经放置了两个1和一个0。因此，在放置另一个1之前，你最多只能再放置一个0。可能是一个起点... - Pandu
“k”的限制是什么？ - rendon
"k" 受到 "10^9" 的限制。我已经更新了问题。 - abc
好的，基本上，你有第一个匹配k=3的数字是000111，那么第二个数字将是000111 + 111，即01110，对于k=4，你将得到00001111，然后加上1111，所以你得到了第二个匹配的数字，即00011110，依此类推。如果我错了，请纠正我。 - mamdouh alramadan
这部分是一个组合问题，因此您可以在http://math.stackexchange.com/上提问以获得一些好的见解。只需用“A”和“B”替换您的“0”和“1”，并且不要提到“二进制”这个词;-) - Digital Trauma
你错了。请阅读安迪·琼斯的回复。你的数字是错误的，主要因为00011110包含前缀0001111，不符合第二个属性。 - abc
2个回答
4
您描述的数字对应于 Dyck words。 Kasa 2009的第二部分提供了一种简单的算法，以字典顺序枚举它们。如果您想进行进一步阅读，它的参考资料应该很有帮助。
另外（请注意我在写这篇文章时已经半睡半醒，所以可能有错误），维基百科文章指出长度为2n的Dyck单词的数量是第n个Catalan数C(n)。您可能需要找到最小的n，使得C(n)大于您正在寻找的k，然后从X^n Y^n开始枚举Dyck单词。
我会搜索相关信息并尝试自己解决，如果无法成功，我一定会回来的，所以+1 ATM。 - abc
问题已解决。逐个生成的速度太慢了，但在阅读有关卡特兰数的文档和知识后，我想出了更快的算法。 - abc
可以分享一下你采用的算法或代码吗？这样其他人如果遇到同样的问题也能够解决。 - Andy Jones
1
我已经根据您的建议编辑了问题并分享了一个想法。 - abc
0

上次我对这个问题的理解有误，非常抱歉。现在我已经进行了修改，可以保证纠正，并且您可以先测试代码。复杂度为O(n^2)，详细答案如下：

首先，我们可以将问题归结为下一个问题

我们正在寻找满足以下条件的第k大数字(k受到10^9的限制):

  • 1's的数量等于0's的数量，可以描述如下：#(1) = #(0)
  • 这个数字的每个前缀都必须至少包含与之相同数量的[[1's和0's]]，这意味着：没有前缀会包含比1's更多的[[0's]]。

让我们举一个例子来解释它：假设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<=m<=2n}只能是1或0，让DP[v][q]表示满足条件2和条件#(1)=q的数字数量，在{A[2n-v+1]~A[2n]}中，所以DP[2n][n]是满足条件的数字数量。

A[1] 只能是 1 或 0，如果 A[1]=1，数字的数量为 DP[2n-1][n-1]，如果 A[1]=0，数字的数量为 DP[2n-1][n]，现在我们想要找到第 k 大的数字，如果 k<=DP[2n-1][n-1]，kth largest 数字的 A[1] 必须是 1，然后我们可以用 DP[2n-2][n-2] 判断 A[2]；如果 k>DP[2n-1][n-1]，kth largest 数字的 A[1] 必须是 0，且 k=k-DP[2n-1][n-1]，然后我们可以用 DP[2n-2][n-1] 判断 A[2]。因此，按照相同的理论，我们可以逐个判断 A[j]，直到没有数字可比较。现在我们可以举一个例子来理解 (n=3, k=4)

我们使用动态规划来确定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<=19 的情况，在问题中 n<1000，因此您可以使用大数编程，并且该代码可以通过位运算进行优化，因此该代码仅供参考。
/*-------------------------------------------------- 
    Environment: X86 Ubuntu GCC 
    Author: Cong Yu 
    Blog: aimager.com                              
    Mail: funcemail@gmail.com                      
    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;
}
打印所有的第k个数字？这里只有一个。作为输入，我已经给出了n，它是位数乘以二，而k告诉我我们要查找的数字。作为输出，我们必须写一行包含该数字的二进制形式的代码。 - abc
@Kostek：我已经修改了我的答案，你可以看一下。 - AImager
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接