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

Question

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;
}

What does "at fault" mean? And did you search previous questions? — Potatoswatter, May 01 '10 at 00:27
possible duplicate of http://stackoverflow.com/questions/2211915/combination-and-permutation-in-c http://stackoverflow.com/questions/2685501/c-next-permutation-for-combinations-or-subsets-in-powerset http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — Potatoswatter, May 01 '10 at 00:28

score 2 · Answer 1 · answered May 01 '10 at 00:11

2

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.

answered May 01 '10 at 00:11

Billy ONeal

104,103
58
317
552

well, is not a permutation I'm looking for, is a combination I'm looking for, so for instance in 1 2 3 4 , 3 out of 4 would be 1 2 3 1 2 4 1 3 4 2 3 4 – Mark May 01 '10 at 00:14
@mark: You can use binary permutations of length n as a filter. – tiftik May 01 '10 at 00:18
@Vicente Botet Escriba: I misunderstood the meaning of the word "combinations" true, but the example output he is showing is what he should edit into is question. – Billy ONeal May 01 '10 at 03:47

score 2 · Answer 2 · answered Oct 03 '16 at 12:21

This is about as fast as it can be calculated - the actual combination function is done using two lines of code. However, this isn't the most intuitively easy to understand!
The work is done by implementing a Gray code sequence.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <stdint.h>
using namespace std;

//'Combinations' over a set of n objects with k bins, eg n=3,k=2 = 3

//The combination function.
//It takes a combination and returns the next combination.
//It uses GCC's '__builtin_ctzll' which returns the number of
//trailing 0-bits in v, starting at the least significant bit position.
uint64_t combination(uint64_t v) {
    uint64_t t = v | (v - 1ULL); // t gets v's least significant 0 bits set to 1
    return (t + 1ULL) | (((~t & -~t) - 1ULL) >> (__builtin_ctzll(v) + 1ULL));
}

//arg 1 is number of bins (n) arg 2 is number of samples (k/r)
int main (int argc, char *argv[]) {
    uint64_t n = min(64ULL,argc > 1ULL ? atoi(argv[1]) : 3ULL); //max bins = 63
    uint64_t k = min( n,argc > 2 ? atoi(argv[2]) : 2ULL);       //max samples = bins.
    uint64_t v = (1ULL << k) - 1;       //start value;
    uint64_t m = n == 64 ? UINT64_MAX: (1ULL << n) - 1ULL;  //size of n is used as a mask.
    string index = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz+*";
    cout << index.substr(0,n) << endl;
    do {
        cout << bitset<64>(v & m).to_string().substr(64ULL-n) << endl;
        v=combination(v);
    } while (v < m);
    return 0;
}

salva · Answer 3 · 2011-01-19T15:28:54.053

Consider that your iterator is a number of k digits in base n. In C/C++ you can represent it as an array of ints of size k where every element is in the range from 0 to n-1).

Then, to iterate from one position to the next you only need to increment the number.

That will give you all the permutations. In order to get combinations you have to impose an additional condition that is that digits must be in ascending order.

For instance with k = 3, n = 3: 000 001 002 011 012 022 111 112 122 222

Implementing that constraint in C is also pretty simple, on the increment operation used to iterate, instead of setting the rightmost digits to zero when there is a carry, you have to set them to the same value as the leftmost digit changed.

update: some code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXK 100

int
main(int argc, char *argv[]) {
    int digits[MAXK];

    int k = atol(argv[1]);
    int n = atol(argv[2]);
    int i, left;

    memset(digits, 0, sizeof(digits));

    while(1) {
        for (i = k; i--; ) {
            printf("%d", digits[i]);
            printf((i ? "-" : "\n"));
        }

        for (i = k; i--; ) {
            left = ++digits[i];
            if (left < n) {
                while (++i < k) digits[i] = left;
                break;
            }
        }
        if (i < 0) break;
    }
}

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

3 Answers3