I need help creating a k-combinations algorithm non-recursively

Question

I've looked around online for an non-recursive k-combinations algorithm, but have had trouble understanding all of the reindexing involved; The code I've found online is not commented well, or crashes.

For example, if I have the collection, {'a', 'b', 'c', 'd', 'e'} and I want to find a 3 combinations; ie,

abc abd abe acd ace ade bcd bce bde cde

How can I implement an algorithm to do this? When I write down the general procedure, this it is clear. That is; I increment the last element in a pointer until it points to 'e', increment the second to last element and set the last element to the second to last element + 1, then increment the last element again until it reaches 'e' again, and so on and so forth, as illustrated by how I printed the combinations. I looked at Algorithm to return all combinations of k elements from n for inspiration, but my code only prints 'abc'. Here is a copy of it:

#include <stdio.h> #include <stdlib.h> static void comb(char *buf, int n, int m) { // Initialize a pointer representing the combinations char *ptr = malloc(sizeof(char) * m); int i, j, k; for (i = 0; i < m; i++) ptr[i] = buf[i]; while (1) { printf("%s\n", ptr); j = m - 1; i = 1; // flag used to denote that the end substring is at it's max and // the j-th indice must be incremented and all indices above it must // be reset. int iter_down = 0; while((j >= 0) && !iter_down) { // if (ptr[j] < (n - i) ) { iter_down = 1; ptr[j]++; for (k = j + 1; k < m; k++) { ptr[k] = ptr[j] + (k - j); } } else { j--; i++; } } if (!iter_down) break; } } int main(void) { char *buf = "abcde"; comb(buf, 5, 3); return 1; }

(1)char *ptr = malloc(sizeof(char) * m); --> char *ptr = malloc(sizeof(char) * (m+1)); — BLUEPIXY
– BLUEPIXY, Commented May 8, 2014 at 10:40
(2)if (ptr[j] < (n - i) ) { : It has compared the letters and numbers. It is always false case of this sample code.(j--... only once "abc") — BLUEPIXY
– BLUEPIXY, Commented May 8, 2014 at 10:42
Thanks for the help, but I ended up implementing it using a different method. — user1876508
– user1876508, Commented May 8, 2014 at 16:52

user2357112 · Accepted Answer · 2014-05-08 03:00:12Z

The very big problem with your code is mixing up indices and values. You have an array of chars, but then you try to increment the chars as if they were indices into the buffer. What you really need is an array of indices. The array of chars can be discarded, since the indices provide all you need, or you can keep the array of chars separately.

You were right. I was attempting to do two things at once, which created a lot of unneeded complexity.

user1876508 · Accepted Answer · 2014-05-08 17:07:36Z

I found a psuedocode description here, http://www4.uwsp.edu/math/nwodarz/Math209Files/209-0809F-L10-Section06_03-AlgorithmsForGeneratingPermutationsAndCombinations-Notes.pdf and implemented it in C by

#include <stdlib.h> #include <stdio.h> // Prints an array of integers static void print_comb(int *val, int len) { int i; for (i = 0; i < len; i++) { printf("%d ", val[i]); } printf("\n"); } // Calculates n choose k static int choose(int n, int k) { double i, l = 1.0; double val = 1.0; for (i = 1.0; i <= k; i++) { l = ((double)n + 1 - i) / i; val *= l; } return (int) val; } static void comb(int n, int r) { int i, j, m, max_val; int s[r]; // Initialize combinations for (i = 0; i < r; i++) { s[i] = i; } print_comb(s, r); // Iterate over the remaining space for (i = 1; i < choose(n, r); i++) { // use for indexing the rightmost element which is not at maximum value m = r - 1; // use as the maximum value at an index, specified by m max_val = n - 1; // use for while(s[m] == max_val) { m--; max_val--; } // increment the index which is not at it's maximum value s[m]++; // iterate over the elements after m increasing their value recursively // ie if the m-th element is incremented, all elements afterwards are // incremented by one plus it's offset from m // For example, this is responsible for switching 0 3 4 to 1 2 3 in // comb(5, 3) since 3 and 4 in the first combination are at their maximum // value for (j = m; j < r - 1; j++) { s[j + 1] = s[j] + 1; } print_comb(s, r); } } int main(void) { comb(5, 3); return 1; }

Collectives™ on Stack Overflow

I need help creating a k-combinations algorithm non-recursively

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related