Non-recursive approach to the problem of generating combinations with an error

Question

I need a non-recursive approach to the problem of generating a combination of a specific set of characters or numbers.

So, given the subset of k numbers n, print the whole possible combination n! / K! (nk)!

The recursive method will give a combination, given the previous combination.

The non-recursive method generates a combination of the given value of the loop index i .

I addressed a problem with this code:

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

This is due to the fact that (nk)! in the case n = 4 and k = 3 is equal to 1. and if k> 3, will it 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(nk) / 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 are looking for, and does not require you to write (and debug and maintain) your own.

Answer 2

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

Then, to iterate from one position to another, you only need to increase the number.

This will give you all the permutations. To get combinations, you must impose an additional condition that the numbers must be in ascending order.

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

Implementing this restriction in C is also quite simple in the increment operation used for iteration, instead of setting the rightmost digits to zero, when there is hyphenation, you should set them to the same value as the leftmost digit.

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

Answer 3

This is about as fast as it can be calculated - the actual combination function is performed using two lines of code. However, this is not the most intuitive! Work is done by implementing a sequence of Gray code.

 #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 '__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 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; }