wu :: forums - Print Page


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

        riddles >> cs >> ways of selecting k non consecutive items from n
        
(Message started by: tombstone on Jan 30^th, 2010, 11:20pm)

Title: ways of selecting k non consecutive items from n
Post by tombstone on Jan 30^th, 2010, 11:20pm

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.

Title: Re: ways of selecting k non consecutive items from
Post by birbal on Jan 31^st, 2010, 12:03am

on 01/30/10 at 23:20:24, 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 :|

Title: Re: ways of selecting k non consecutive items from
Post by tombstone on Jan 31^st, 2010, 12:25am

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.

Title: Re: ways of selecting k non consecutive items from
Post by towr on Jan 31^st, 2010, 2:36am

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

Title: Re: ways of selecting k non consecutive items from
Post by tombstone on Jan 31^st, 2010, 4:22am

@towr
I have two doubts,
1) the complexity of calculating C(n-k+1,k) . Isn't it O(n ²) when you memoize the intermediate results , which also requires O(n²) space. If you don't memoize then wont the cost of calculating ⁿC_k 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

Title: Re: ways of selecting k non consecutive items from
Post by towr on Jan 31^st, 2010, 6:46am

on 01/31/10 at 04:22:27, tombstone wrote:

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

Title: Re: ways of selecting k non consecutive items from
Post by towr on Jan 31^st, 2010, 7:17am

on 01/31/10 at 04:22:27, 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.

Title: Re: ways of selecting k non consecutive items from
Post by tombstone on Jan 31^st, 2010, 8:43am

@towr
you made it very very clear . :)

Quote:

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