Algorithm for finding kth binary number with certain properties

Question

Let's assume we will consider binary numbers which has length 2n and n might be about 1000. We are looking for kth number (k is limited by 10^9) which has following properties:

• Amount of 1's is equal to amount of 0's what can be described as following: #(1) = #(0)
• Every prefix of this number has to contain atleast as much 0's as 1's. It might be easier to understand it after negating the sentence, which is: There is no prefix which would contain more 1's than 0's.

And basically that's it. So to make it clear let's do some example: n=2, k=2 we have to take binary number of length 2n:

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

And now we have to find 2nd number which fulfill those two requirements. So we see 0011 is the first one, and 0101 is second one. If we change k=3, then answer doesn't exist since there are number which have same amount of opposite bits, but for 0110, there is prefix 011 so number doesn't fulfill second constraint and same would be with all numbers which has 1 as most significant bit.

So what I did so far to find algorithm?

Well my first idea was to generate all possible bits settings, and check whether it has those two properties, but generate them all would take O(2^(2n)) which is not an option for n=1000.

Additionally I realize there is no need to check all numbers which are smaller than 0011 for n=2, 000111 for n=3, and so on... frankly speaking those which half of most significant bits remains "untouched" because those numbers have no possibility to fulfill #(1) = #(0) condition. Using that I can reduce n by half, but it doesn't help much. Instead of 2 * forever I have forever running algorithm. It's still O(2^n) complexity, which is way too big.

Any idea for algorithm?

Conclusion

This text has been created as a result of my thoughts after reading Andy Jones post.

First of all I wouldn't post code I have used since it's point 6 in following document from Andy's post Kasa 2009. All you have to do is consider nr as that what I described as k. Unranking Dyck words algorithm, would help us find out answer much faster. However it has one bottleneck.

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

Considering that n <= 1000, Catalan number can be quite huge, even C(999,999). We can use some big number arithmetic, but on the other hand I came up with little trick to overpass it and use standard integer.

We don't want to know how big actually Catalan number is as long as it's bigger than k. So now we will create Catalan numbers caching partial sums in n x n table.

...                                     ...
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     ...

To generate it is quite trivial:

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

So what we can see only this:

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

can cause overflow.

Let's stop at this point and provide definition.

k-flow - it's not real overflow of integer but rather information that value of C(x,y) is bigger than k.

My idea is to check after each running of above formula whether C(x,y) is grater than k or any of sum components is -1. If it is we put -1 instead, which would act as a marker, that k-flow has happened. I guess it quite obvious that if k-flow number is sum up with any positive number it's still be k-flowed in particular sum of 2 k-flowed numbers is k-flowed.

The last what we have to prove is that there is no possibility to create real overflow. Real overflow might only happen if we sum up a + b which non of them is k-flowed but as sum they generated the real overflow.

Of course it's impossible since maximum value can be described as a + b <= 2 * k <= 2*10^9 <= 2,147,483,647 where last value in this inequality is value of int with sign. I assume also that int has 32 bits, as in my case.

Answer 1

The numbers you are describing correspond to Dyck words. Pt 2 of Kasa 2009 gives a simple algorithm for enumerating them in lexicographic order. Its references should be helpful if you want to do any further reading.

As an aside (and be warned I'm half asleep as I write this, so it might be wrong), the wikipedia article notes that the number of Dyck words of length 2n is the n th Catalan number, C(n). You might want to find the smallest n such that C(n) is larger than the k you're looking for, and then enumerate Dyck words starting from X^n Y^n.

Answer 2

I'm sorry for misunderstood this problem last time, so I edit it and now I can promise the correction and you can test the code first, the complexity is O(n^2), the detail answer is follow

---

First, we can equal the problem to the next one

We are looking for kth largest number (k is limited by 10^9) which has following properties:

• Amount of 1's is equal to amount of 0's what can be described as following: #(1) = #(0)
• Every prefix of this number has to contain at least as much [[1's as 0's]], which means: There is no prefix which would contain more [[0's than 1's]].

Let's give an example to explain it: let n=3 and k=4, the amount of satisfied numbers is 5, and the picture below has explain what we should determine in previous problem and new problem:

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

so after we solve the new problem, we just need to bitwise not.

Now the main problem is how to solve the new problem. First, let A be the array, so A[m]{1<=m<=2n} only can be 1 or 0, let DP[v][q] be the amount of numbers which satisfy condition2 and condition #(1)=q in {A[2n-v+1]~A[2n]}, so the DP[2n][n] is the amount of satisfied numbers.

A[1] only can be 1 or 0, if A[1]=1, the amount of numbers is DP[2n-1][n-1], if A[1]=0, the amount of numbers is DP[2n-1][n], now we want to find the kth largest number, if k<=DP[2n-1][n-1], kth largest number's A[1] must be 1, then we can judge A[2] with DP[2n-2][n-2]; if k>DP[2n-1][n-1], kth largest number's A[1] must be 0 and k=k-DP[2n-1][n-1], then we can judge A[2] with DP[2n-2][n-1]. So with the same theory, we can judge A[j] one by one until there is no number to compare. Now we can give a example to understand (n=3, k=4)

(We use dynamic programming to determine DP matrix, the DP equation is 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

If you have not understand clearly, you can use the code to understand

Intention：DP[2n][n] increase very fast, so the code can only work when n<=19, in the problem n<1000, so you can use big number programming, and the code can be optimize by bit operation, so the code is just a reference

/*-------------------------------------------------- 
    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;
}