Author |
Topic: nth element of series (Read 3882 times) |
|
baskin
Newbie
Gender: 
Posts: 26
|
 |
nth element of series
« on: Apr 7th, 2006, 1:09am » |
 Quote  Modify
|
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);
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: nth element of series
« Reply #1 on: Apr 7th, 2006, 9:55am » |
Quote Modify
|
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);
}
|
|
|
| « Last Edit: Apr 13th, 2006, 12:19am by Barukh » |
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: nth element of series
« Reply #2 on: Apr 12th, 2006, 7:07am » |
Quote Modify
|
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+rCm>=n. leftmost (m+r)th bit must be 1.
Then remaining part of the binary string is (n-(m+r-1Cm-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 ? 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: nth element of series
« Reply #3 on: Apr 13th, 2006, 12:21am » |
Quote Modify
|
on Apr 12th, 2006, 7:07am, 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)).
|
|
IP Logged |
|
|
|
knuther
Newbie
Posts: 6
|
|
Re: nth element of series
« Reply #4 on: May 18th, 2006, 11:48am » |
Quote Modify
|
And
Shouldn't this statement
>> if (n == 1) return (1 << m) - 1;
be
>> if (n == 1) return 1 << (m- 1);
??
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7528
|
|
Re: nth element of series
« Reply #5 on: Feb 5th, 2007, 2:02am » |
Quote Modify
|
No, but you could add the statement:
if (m == 1) return 1 << (n - 1);
|
|
IP Logged |
|
|
|
labrin
Newbie
Posts: 9
|
|
Re: nth element of series
« Reply #6 on: Jun 29th, 2007, 11:12pm » |
Quote Modify
|
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;
}
}
}
|
| « Last Edit: Jun 29th, 2007, 11:25pm by labrin » |
IP Logged |
|
|
|
Mr.Unknown
Newbie
Posts: 4
|
|
Re: nth element of series
« Reply #7 on: Jul 6th, 2007, 8:03am » |
Quote Modify
|
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 30th 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;
}
|
|
|
|
IP Logged |
|
|
|
fakrudeen
Newbie
Posts: 5
|
|
Re: nth element of series
« Reply #8 on: Sep 28th, 2008, 12:46pm » |
Quote Modify
|
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) Ck to (m+k)Ck+1
calcuation requires multiplying by (m+k)/(k+1)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: nth element of series
« Reply #9 on: Sep 28th, 2008, 1:34pm » |
Quote Modify
|
on Sep 28th, 2008, 12:46pm, 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) Ck to (m+k)Ck+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.
|
| « Last Edit: Sep 28th, 2008, 1:36pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fakrudeen
Newbie
Posts: 5
|
|
Re: nth element of series
« Reply #10 on: Sep 28th, 2008, 3:22pm » |
Quote Modify
|
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-1Ck to the running sum.
While Barukh calculated the running sum by
m+k-1Ck + m+k-1Ck-1
=m+kCk
because m+k-1Ck-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);
}
|
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print