Author |
Topic: ways of selecting k non consecutive items from n (Read 1664 times) |
|
tombstone
Newbie
Posts: 14
|
 |
ways of selecting k non consecutive items from n
« on: Jan 30th, 2010, 11:20pm » |
 Quote  Modify
|
In how many ways can we select k non consecutive items from a list of n items. solution should have a time complexity of O(nk) and space complexity of O(n)! 
Having solution with time complexity of O(nk) is easy. what stumps me is the space constraint.
|
| « Last Edit: Jan 31st, 2010, 12:26am by tombstone » |
 IP Logged |
|
|
|
birbal
Full Member
Gender: 
Posts: 250
|
|
Re: ways of selecting k non consecutive items from
« Reply #1 on: Jan 31st, 2010, 12:03am » |
Quote Modify
|
on Jan 30th, 2010, 11:20pm, tombstone wrote:| In how many ways can we select k non consecutive items from a list of n items. solution should have a time complexity of O(nk) and space complexity of O(n)! |
|
Isn't it a combinatorics problem ? or am i understanding it wrong :|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
tombstone
Newbie
Posts: 14
|
|
Re: ways of selecting k non consecutive items from
« Reply #2 on: Jan 31st, 2010, 12:25am » |
Quote Modify
|
The term Non consecutive makes it tricky and therefore its easier to write a recursion . Well the combinatorics solution you are talking of will be the closed form of the recursion.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ways of selecting k non consecutive items from
« Reply #3 on: Jan 31st, 2010, 2:36am » |
Quote Modify
|
One way to consider it is that if you pick an item, you also pick the next one. (Except when you pick the last one.)
case 1: you pick the last item, you need the number of rearrangements to have K-1 (consecutive) pairs and N-2K+1 singles, which is C(N-K, K-1)
case 2: you don't pick the last item, you need the number of rearrangements of K pairs and N-2K singles. Which is C(N-K, K)
Taken together this is C(N-K+1, K)
(Which, incidentally, is what we'd have gotten by just adding an extra element at the back instead of splitting the two cases. Eh, hindsight.)
Time complexity O(N), space O(1).
|
| « Last Edit: Jan 31st, 2010, 2:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
tombstone
Newbie
Posts: 14
|
|
Re: ways of selecting k non consecutive items from
« Reply #4 on: Jan 31st, 2010, 4:22am » |
Quote Modify
|
@towr
I have two doubts,
1) the complexity of calculating C(n-k+1,k) . Isn't it O(n 2) when you memoize the intermediate results , which also requires O(n2) space. If you don't memoize then wont the cost of calculating nCk increase?
2) Can you elaborate on how both the original question and the idea you mentioned are similar. My intuition isn't good enough to understand this  . and also how you put case one as C(N-K,K-1) ( I guess case 2 can be understood in the same way)
The solution I coded was the recurrence below
F(n,k) = F(n-2,k-1)+F(n-1,k)
and I memoized the solutions
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ways of selecting k non consecutive items from
« Reply #5 on: Jan 31st, 2010, 6:46am » |
Quote Modify
|
on Jan 31st, 2010, 4:22am, tombstone wrote:@towr
I have two doubts,
1) the complexity of calculating C(n-k+1,k) . Isn't it O(n 2) when you memoize the intermediate results , which also requires O(n2) space. If you don't memoize then wont the cost of calculating nCk increase? |
|
It's three factorials. If you can't calculate a factorial in constant space and linear time you're doing it wrong 
fac(n)
{
f=1;
for(int i=2; i <= n; i++) f*=i;
return f;
}
Quote:| 2) Can you elaborate on how both the original question and the idea you mentioned are similar. My intuition isn't good enough to understand this . and also how you put case one as C(N-K,K-1) ( I guess case 2 can be understood in the same way) |
|
I'll try to explain it a bit better.
If you pick an item, you can't pick the next one. So they are both "out of the game" so to speak. Evry choice you make, makes two (consecutive) items unavailable for further choice.
So at the end, there are are 2K elements 'chosen' in pairs, of qwhich the first are the elements in your set, and the second of the pair are the elements that can't be chosen if you wanted to go for a K+1st item.
Except, of course, when the last item is in our set, because the next after doesnt' exist (although it can therefore not be chosen). But we can imagine there is a next-after-last virtual item to solve this.
So this means, we have chosen K consecutive pairs, from N+1 items. Of each pair, the first is in our set, the second is one that couldn't be chose because the one before it was.
That leaves N+1-2K elements that are unaccounted for, that are intersperced before and after the K pairs.
The number of ways to arrange X and Y elements, is (X+Y)!/(X!*Y!). In our case these are X=N+1-2K single elements, and Y=K consecutive pairs. So that gives (N+1-K)!/((N+1-2K)!*K!), or in shorter notation C(N-K+1,K).
For example, if we have a,b,c,d,e,f and want 2 elements
we can have
(a,b),(c,d),e,f,*
(a,b),c,(d,e),f,*
(a,b),c,d,(e,f),*
(a,b),c,d,e,(f,*)
a,(b,c),(d,e),f,*
a,(b,c),d,(e,f),*
a,(b,c),d,e,(f,*)
a,b,(c,d),(e,f),*
a,b,(c,d),e,(f,*)
a,b,c,(d,e),(f,*)
(6-2+1)!/((6-4+1)!*2!) = 5!/(3!*2!) = 10
(bold are the chosen elements, the ones stricken through are the unchoosable ones, and * is the fictitious N+1st element to complete the last pair.)
|
| « Last Edit: Jan 31st, 2010, 7:14am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: ways of selecting k non consecutive items from
« Reply #6 on: Jan 31st, 2010, 7:17am » |
Quote Modify
|
on Jan 31st, 2010, 4:22am, tombstone wrote:The solution I coded was the recurrence below
F(n,k) = F(n-2,k-1)+F(n-1,k)
and I memoized the solutions |
|
A better way is to use dynamic programming, and use the fact you only need to keep two columns ( F(n-2, :) and F(n-1, :) ) to calculate the next one.
So that 3 columns of k elements in memory at a time, or O(k) memory.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
tombstone
Newbie
Posts: 14
|
|
Re: ways of selecting k non consecutive items from
« Reply #7 on: Jan 31st, 2010, 8:43am » |
Quote Modify
|
@towr
you made it very very clear . 
Quote:A better way is to use dynamic programming, and use the fact you only need to keep two columns ( F(n-2, and F(n-1, ) to calculate the next one.
So that 3 columns of k elements in memory at a time, or O(k) memory. |
|
I actually did a dp but I didn't realize the fact that I need only two columns! So this solves the original problem too! (fits the given (rather required ) constraints )
thanks a lot
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print