a non recursive approach to the problem of generating combinations at fault
- by mark
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(x0) fact*=x--;
return fact;
}
