To print all combinations of length k from n array

[Maggi Iggam]

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)

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

[coder777]

Imagine the following:

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?

[Maggi Iggam]

Umm... I couldn't get the idea ? what does it mean 'can combine with' ??

Well , you noticed very right @coder777 :D . But this time concept/algorithm is quite clear but implementing it down to code also troubling me .

[mik2718]

Your code for k = 2 should be more like this

//if k=2
for (i=0;i<n-1;i++) {
 for (j=i+1;j<n;j++) {
  cout<<i<<","<<j<<endl;
 }
} 

but this only cuts total time down by a factor of 2.

for k=400 I think you have an impossible problem


edit
If k=400 and N=1000 then the total number of combinations is
1000 choose 400
I suspect this is larger than the number of atoms in the universe

[Gaminic]

What coder777 was hinting at is that the case for N numbers and size K, the options are {1, {K-1 combinations}) to {N, {K-1 combinations}}.

[cronopio]

Hi, this example containing all permutations in array,

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
int myints[] = {1,2,3};

cout << "The 3! possible permutations with 3 elements:\n";

sort (myints,myints+3);

do {
cout << myints[0] << " " << myints[1]<< endl;
} while ( next_permutation (myints,myints+3) );

system("pause");
}

Now your problem is regulate for k=2.

Alex

[coder777]

What coder777 was hinting

Well, yes, sure, I didn't miss the point or so...
and does this damned computer swallow typings?

Now your problem is regulate for k=2.

Yes, and that's exactly what takes the fun out of funeral

this kind of problem requires a new concept: recursion
since it's easier to show than tell:

int combinations[401];
void print_combinations(int k_offs, int k, int n_offs, int n)
{
  for(int i = n_offs; i <= n; ++i)
  {
    combinations[k_offs] = i;
    if((k - k_offs) == 1)
    {
      for(int i = 1; i <= k_offs; ++i)
      {
        if(i > 1)
          cout << ", ";
        cout << combinations[k_offs];
      }
      cout << endl;
    }
    else
      print_combinations(k_offs + 1, k, i + 1, n);
  }
}

This is pure theory! Test it! Hope you get it?

[Maggi Iggam]

@mike2718 : Neverthless dude , both codes give O(n) time so it doesn't matter if we cut down by 2 :)

@cronopio : Yeah i have seen this in algo/next_permutation but here i dont think this helps me :)

@Gaminic : Yeah i think i got it by now !

@coder777 : thanks man i got it !!! Cheers to your programme , it works like magic :D

[coder777]

A little tweak has to be done (til it work):

int combinations[401] = { 0 };
void print_combinations(int k_offs, int k, int n_offs, int n)
{
  for(int i = n_offs; i <= n; ++i)
  {
    combinations[k_offs] = i;
    if((k - k_offs) > 0)
      print_combinations(k_offs + 1, k, i + 1, n);
    else
    {
      for(int j = 1; j <= k_offs; ++j)
      {
        if(j > 1)
          std::cout << ", ";
        std::cout << combinations[j];
      }
      std::cout << std::endl;
    }
  }
}

The trick is the reduction. There're not so many unique combinations

[mik2718]

Actually the nested loops give O(n^2) runtime.

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)

[coder777]

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

[mik2718]

I make it that you have n slots and you choose k of them for each output, giving n choose k outputs

This is n!/k!(n-k)! so its actually biggest when k = n/2 and smallest when k=n O(1) or k=0 O(1)

I don't know how to translate O(n!/k!(n-k)!) into the usual polynomial format

[Maggi Iggam]

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 !!!

[coder777]

it solved my problem !!!

Okay, but it's nevertheless interesting to find out the big o. And yes, mik2718 spot it right it is actually the "n choose k" algorithm

[Maggi Iggam]

Yeah , this can become good source for others :)

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