wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find Nth Number In the Binary Sequence 
        
(Message started by: R0B1N on Jun 21^st, 2007, 11:29pm)

Title: Find Nth Number In the Binary Sequence
Post by R0B1N on Jun 21^st, 2007, 11:29pm

Write a function

Code:

int _findNth(int n, int x)
{

//code here
}

The function must return the nth number in the sequence of binary numbers with exactly x ones.

example :
if n=5, x=3 ; then findn(5,3) must return 19 (i.e. 10110).
111, 1011, 1101, 1110,10011,10101,10110...

Here the Function should return DecimalValueof (10011);

Any Better Approach than the Obvious O(N) method ? (//the one which generates number in sequence and checks for number of one's )

Another Way is to do Something like , Say for 32 bit numbers , Generate permutations with X numbers of one and 32-X zero's . But Am not able to figure out how to do this as to get the numbers in Sorted order

Title: Re: Find Nth Number In the Binary Sequence
Post by towr on Jun 22^nd, 2007, 1:02am

Well, there are choosenk(32,x) valid bitstrings to start with.
You can probably do something recursive, like first determine if the first bit is 1. If the first bit is 1, then n must be among the first choosenk(31,x-1) bitstrings.
If it's not, take n=n-choosenk(31,x-1), and continue for the next 31 bits in a similar way.

Or something like that.

In any case we have choosenk(n,x)=choosenk(n-1,x-1)+choosenk(n-1,x)

Title: Re: Find Nth Number In the Binary Sequence
Post by Barukh on Jun 22^nd, 2007, 2:42am

Here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1144397342;start=1#1).

Title: Re: Find Nth Number In the Binary Sequence
Post by labrin on Jun 29^th, 2007, 11:12pm

complexity is O(m)...where m is the no of bits in nth seq.
assuming factorial() takes O(1) time.
findN(int n, int ones)
{ zeroes = 0;
while( fact( zeroes+ones) / ( fact(zeroes) * fact(ones) ) < n )
zeroes++;
while( ( zeroes + ones)>0)
{ ways= fact( zeroes+ones) / ( fact(zeroes) * fact(ones) );
y = ways / ( zeroes + ones);
if( zeroes*y >=n )
{ print(" 0 "); zeroes--;
}
else
{ print("1"); ones--;
n = n - zeroes*y;
}
}
}

Title: Re: Find Nth Number In the Binary Sequence
Post by randome on Jul 15^th, 2007, 11:49am

Why can't you just start with the smallest number possible that has x bits

so if x = 3;
start with 111.

Use the following method:
If there are no 0s which have 1s following them insert a 0 after the leading bit.

if there are 0s with 1s after it swap the most significant 1 with the 0.

111 (N=1) -> 1011 -> 1101 -> 1110 -> 10110 (insert 0 since there are non empty slots to swap)

Title: Re: Find Nth Number In the Binary Sequence
Post by pex on Jul 15^th, 2007, 11:57am

on 07/15/07 at 11:49:48, randome wrote:

... 1110 -> 10110

What happened to 10011 and 10101?

Title: Re: Find Nth Number In the Binary Sequence
Post by sk on Sep 4^th, 2007, 8:18pm

the swap idea works.
some abstractions used
BitSwap(a,i,j) - swaps the bits i,j of integer a

Code:

void BitSwap(a,x,y)
{

//A better impl is defenitely possible
int t1=t2=1;
for(int i=0;i<x;i++)
t1<<1;

for(int i=0;i<y;i++)
t2<<1;

t1 = a&t1;
t2 = a&t2;
a= a&t1&t2;
}

int _findNth(int n, int x)
{
int count=1, current, a, pos; //max is 16 bits
current = 2 * pow(x) -1;

for(int i=x; count<n;i--) //counting bits from right
{
pos = i; //position of the bit
a = current;
while(pos >0 && count < n)
{
if(pos == i)
current = a;
BitSwap(a, pos, pos-1); //bit swap
count++;
pos--;
}
}
return a;
}