a non recursive approach to the problem of generating combinations at fault

Question

Hi,

I wanted a non recursive approach to the problem of generating combination of certain set of characters or numbers.

So, given a subset k of numbers n, generate all the possible combination n!/k!(n-k)!

The recursive method would give a combination, given the previous one combination.

A non recursive method would generate a combination of a given value of loop index i.

I approached the problem with this code:

Tested with n = 4 and k = 3, and it works, but if I change k to a number > 3 it does not work.

Is it due to the fact that (n-k)! in case of n = 4 and k = 3 is 1. and if k > 3 it will be more than 1?

Thanks.

int facto(int x);

int len,fact,rem=0,pos=0;
int str[7];
int avail[7];


   str[0] = 1;
   str[1] = 2;
   str[2] = 3;
   str[3] = 4;
   str[4] = 5;
   str[5] = 6; 
   str[6] = 7;




  int tot=facto(n) / facto(n-k) / facto(k);




for (int i=0;i<tot;i++)
{


       avail[0]=1;
       avail[1]=2;
       avail[2]=3;
       avail[3]=4;
       avail[4]=5; 
       avail[5]=6;
avail[6]=7;



    rem = facto(i+1)-1;
    cout<<rem+1<<". ";
    for(int j=len;j>0;j--)
    {
        int div = facto(j); 
        pos = rem / div; 
        rem = rem % div; 
        cout<<avail[pos]<<" "; 
        avail[pos]=avail[j];

    }
    cout<<endl;
}

int facto(int x)
{
    int fact=1;
    while(x>0) fact*=x--;
    return fact;
}

Answer 1

Err.. why not use std::next_permutation? It does exactly what you're looking for and doesn't require you to write (and debug and maintain) your own.