wu :: forums - Print Page


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

        riddles >> cs >> nth element of series
        
(Message started by: baskin on Apr 7^th, 2006, 1:09am)

Title: nth element of series
Post by baskin on Apr 7^th, 2006, 1:09am

find the nth element of the series defined as:

1) each elemnt has the same no of bits (m) set to one in its binary representation

2) series is in ascending order

you have to give the fn :

int fun(int n, int m);

Title: Re: nth element of series
Post by Barukh on Apr 7^th, 2006, 9:55am

How about this (no explanations for now)?

Code:

int fun(int n, int m)
{
if (n == 1) return (1 << m) - 1;

int p = m, C = 1, Cp;

do {
p++;
Cp = C;
C = C * p / (p-m);
} while (C < n);

return (1 << p-1) + fun(n-Cp, m-1);
}

Title: Re: nth element of series
Post by inexorable on Apr 12^th, 2006, 7:07am

Barukh, I guess the last line should be
return (1 << p-1) + fun(n-Cp, m-1); instead of
return (1 << p-1) + fun(m-1, n-Cp);

Btw Your code is mesmerising :).
From what I understand is , You are finding minimum length of bit string required to get nth number having m bits. i.e smallest ^m+rC_m>=n. leftmost (m+r)th bit must be 1.
Then remaining part of the binary string is (n-(^m+r-1C_m-1))th number containing m-1 bits which explains the recursive call.

here Space complexity is O(m).
I was wondering what the worst case time complexity is ? ???

Title: Re: nth element of series
Post by Barukh on Apr 13^th, 2006, 12:21am

on 04/12/06 at 07:07:56, inexorable wrote:

Barukh, I guess the last line should be
return (1 << p-1) + fun(n-Cp, m-1); instead of
return (1 << p-1) + fun(m-1, n-Cp);

Yes, of course. Thanks for clarifying.

Quote:

Btw Your code is mesmerising :).

Thank you for your appreciation.

Quote:

I was wondering what the worst case time complexity is ? ???

I would estimate it as O(m log(n)).

Title: Re: nth element of series
Post by knuther on May 18^th, 2006, 11:48am

And

Shouldn't this statement

>> if (n == 1) return (1 << m) - 1;

be

>> if (n == 1) return 1 << (m- 1);

??

Title: Re: nth element of series
Post by Grimbal on Feb 5^th, 2007, 2:02am

No, but you could add the statement:
if (m == 1) return 1 << (n - 1);

Title: Re: nth element of series
Post by labrin on Jun 29^th, 2007, 11:12pm

complexity is O(m)..where m is no of bits to represent 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: nth element of series
Post by Mr.Unknown on Jul 6^th, 2007, 8:03am

Let me first admit that I found the answer @ http://www.hackersdelight.org/basics.pdf

Represent the binary number with n bits set as (0+1)*01⁺0*
Let Prefix be the pattern which is matched as (0+1)*
Remaining String 'str' is 01⁺0*

Supposing that 'str' is r-bit word with k 1's
the next smallest number will have the same prefix but str will be " 1 0{r-k}1{k-1} "

0{r-k} => r-k zeroes
1{k-1} => k ones

Example :

Consider 30^th smallest number with five bits set is 174 (10101110).

To find the next smallest (31^st) with five bits set ,

Represent 174 as (0+1)*01110

The next smallest number is (0+1)*10011 which is 10110011 - 179

Code:

#include <stdio.h>

unsigned int findn(unsigned int n,unsigned int x)
{

/*
x - no of bits set
n - nth smallest
*/

unsigned smallest, ripple, ones;
unsigned result;
unsigned int i;

result = (1<<x)-1;
for(i=1;i<n;i++)
{
smallest = result & -result;
ripple = result + smallest;
ones = result ^ ripple;
ones = (ones >> 2)/smallest;
result = ripple | ones;
}
return result;

}

int main()
{
printf("%u\n",findn(5,3));
return 0;
}

Title: Re: nth element of series
Post by fakrudeen on Sep 28^th, 2008, 12:46pm

C = C * p / (p-m);
should be,
C += C * p / (p-m);

also there is an off by 1 error in p.

(m+k-1) C_k to (m+k)C_k+1
calcuation requires multiplying by (m+k)/(k+1)

Title: Re: nth element of series
Post by towr on Sep 28^th, 2008, 1:34pm

on 09/28/08 at 12:46:32, fakrudeen wrote:

C = C * p / (p-m);
should be,
C += C * p / (p-m);

also there is an off by 1 error in p.

(m+k-1) C_k to (m+k)C_k+1
calcuation requires multiplying by (m+k)/(k+1)

Let's first try the original algorithm once. I'll take m=2 and n=8
Here's the start of the list for m=2:
0000011
0000101
0000110
0001001
0001010
0001100
0010001
0010010 *
0010100
0011000

From the top,

fun(8,2)
-- p=2, C=1
-- p=3, Cp=1, C=1*3/(3-2)=3
-- p=4, Cp=3, C=3*4/(4-2)=6
-- p=5, Cp=6, C=6*5/(5-2)=15
-- return 10000 + fun(8-6, 1)
---- p=1, C=1
---- p=2, Cp=1, C=1*2/(2-1)=2
---- return 10 + fun(2-1, 0)
------ return 1-1

result 10010
which is correct

Your 'corrections' would change this, so they it would seem to me they can't be correct.

Title: Re: nth element of series
Post by fakrudeen on Sep 28^th, 2008, 3:22pm

Ah... I had arrived at the code below, which looked superficially similar to the code above.

I am sorry, the one above works as well.

the difference is I had explicitly added
number of patterns with k zeros m+k-1C_k to the running sum.

While Barukh calculated the running sum by

m+k-1C_k + m+k-1C_k-1
=m+kC_k

because m+k-1C_k-1
is the previous running sum!

Code:

static int f(int n, int m)
{
if (1 == n) {return (1 << m) - 1;}
int elementsCount = 1;
int k;
int currentLevelValue = 1;
for(k = 1;elementsCount < n;++k)
{
currentLevelValue = currentLevelValue*(m + k - 1)/k;
elementsCount += currentLevelValue;
}
return (1 << (m + (k - 1)- 1)) +
f(n - (elementsCount - currentLevelValue)/*number of bit strings with atmost k meaningful zeros*/, m - 1);
}