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, May 08 '14 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, May 08 '14 at 10:42
Thanks for the help, but I ended up implementing it using a different method. — user1876508, May 08 '14 at 16:52

score 1 · Answer 1 · answered May 08 '14 at 03:00

1

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.

answered May 08 '14 at 03:00

user2357112

260,549
28
431
505

You were right. I was attempting to do two things at once, which created a lot of unneeded complexity. – user1876508 May 08 '14 at 17:10

score 1 · Answer 2 · answered May 08 '14 at 17:07

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

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

2 Answers2