I have an array containing numbers , say {1,2,3} then i have to print unique combination of length k where we know value of k at runtime . So if now k=2 solution would print
1,2
1,3
2,3
Here's my algorithm but it requires k before runtime (ie at compile time)
1 2 3 4 5 6
//if k=2
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
if (i!=j) cout<<i<<","<<j<<endl;
}
}
But problem here is that its very ineffecient,slow and we require k at compile time but we need to take value of k from user and k can be as large as 400 .
1 can be combined with all k - 1 numbers
2 can be combined with all k - 1 numbers except 1 -> k - 2
3 can be combined with all k - 1 numbers except 1 and 2 -> k - 3
got the idea?
One question: You always come with quest regarding algorithm. But programming is more than algorithm. Don't you want to do more?
Then for k=3 you are going to get O(n^3), and so on.
The recursive solution will have the same orders, so I am suprised if you are getting k=400 to work (on an array that is reasonably longer than 400 elements)
no, that it would be O((n - k - 1)^{k} + n * k) if i'm not totally wrong which might very well be the case.
But that's not the point. The point is to accomplish this exercise with the minimum possible effort. The trick is that each iteration takes less circulations which still leads to a lot circulations, but well...
Never mind guys , what i was trying with was printing all possibilities and thats obviously bruteforcing and obviously will not fetch me complete points for k=400 . I was just trying to get a working naive algorithm then later try out for optimum algorithm and so i have got a really fast working code by @coder777 , thanx for it , it solved my problem !!!
I agree with @mik2718 , i don't think any algorithm can get us better than O(n!/k!(n-k)!) as total number of solution is itself n!/k!(n-k)! and best we can do is constant time for each each possibility which makes it O(n!/k!(n-k)!) .
One optimization is possible when the n elements have repetition of elements , then the best we can do is O(n!/(c1! c2! ... ct!)) where c1,c2...ct are number of repetitions of unique elements in n. We can code with same algorithm as coder777 supplied but before that we remove repetetive elements out off n and we can optimally do this in O(n) complexity , so a total of O(nCk+n) which is same as O(nCk) .