More efficient way of listing combinations

Question

Recently I answered one of the many repeated questions of 'How to get all possible combinations of an array of insert data type here. My answer was:

#include <stdio.h>

int main()
{
    /* String for combos to be enumerated */
    char set[4] = { 'a', 'b', 'c', 'd' };
    /* Length of the array */
    int setLength = 4, a, b, c;

    /* This will print all combos that have 1 value. E.g. A, B, C, D */
    for (a = 0; a < setLength; a++) 
    {
        printf("%c : ", set[a]);
    }

    /* This will give the 1st value of the combo */
    for (a = 0; a < setLength; a++)
    {
        /* This will give the 2nd value. Resulting in combos with a length of 2 */
        for (b = 0; b < setLength; b++)         
        {
            printf("%c%c : ", set[a], set[b]);
        }
    }

    /* 1st value */
    for (a = 0; a < setLength; a++)
    {
        /* 2nd value */
        for (b = 0; b < setLength; b++)
        {
            /* 3rd value */
            for (c = 0; c < setLength; c++)
            {
                printf("%c%c%c : ", set[a], set[b], set[c]);
            }
        }
    }

    /* To continue with longer combos simply add more and more for loops */
    printf("\n");
    return 0;
}

However when I looked at other answers to this questions they all involved in-built functions from the language e.g. C#. Therefor my question is: is the way I answered correct, or reliable and if not what would be a more efficient way of doing this without in-built functions.

Why not try a couple of different programs and see which one is faster? By the way your program only seems to work for 4-element sets. This doesn't qualify as solution. — n. m. could be an AI, Mar 25 '16 at 12:39
Unrelated, but in C when you don't want a function you take any arguments you must explicitly say it takes `void` as argument. `int main()` and `int main(void)` means two different things. The first takes an indeterminate number of arguments and the latter takes no arguments. Also, the C specification says that the `main` function should look either like `int main(void)` or `int main(int argc, char *argv[])`, `int main()` is not a valid `main` function. — Some programmer dude, Mar 25 '16 at 12:41
@Joachim Pileborg Thank you, criticism is always welcome as I am still very new to C. — Tristan Arthur, Mar 25 '16 at 12:48
@n.m. Will do, Also I will try to correct the above code so that it works with any amount of elements, thank you for your input. — Tristan Arthur, Mar 25 '16 at 12:48
http://stackoverflow.com/a/12225214/2469027 You don't need it @JoachimPileborg — lost_in_the_source, Mar 25 '16 at 12:50
@Joachim In a function *definition* `()` and `(void)` mean exactly the same thing. — n. m. could be an AI, Mar 25 '16 at 12:58
@n.m., not quite. in the prototype for a function, `()` means that the "function may have parameters, but I'm too lazy to write them out." while `(void)` means "this function does not have any parameters." In C, for the `main()` function, both are allowed, but only the `int main( void )` signature is actually correct. — user3629249, Mar 25 '16 at 19:25

bottaio · Accepted Answer · 2016-03-25T12:59:34.183

You can use simple algorithm with backtracking - a techinque which allowes you to use part of your previous computation to get further values.

Here's the code:

void print_comb_rec(char* values, int n, int length, char* helper)
{
    int i;

    if (length == 0)
    {
        printf("%s : ", helper);
        return;
    }

    for (i = 0; i < n; i++)
    {
        helper[length - 1] = values[i];
        print_comb_rec(values, n, length - 1, helper);
    }
}

void print_comb(char* values, int n, int length)
{
    char* helper = malloc(sizeof(char) * (length + 1));
    int i;

    helper[length] = '\0';
    print_comb_rec(values, n, length, helper);

    free(helper);
}

usage: use a function print_comb. It takes values to permutate, length of an array n and length of the combination. By using it you can get results for given length.

Note that number of possible combinations grows exponentialy (namely it's O(n^length)) for given n. As for any recursive algorithm there is also a possibility to run out of stack's memory using it.

Thank you, this helped a lot. – Tristan Arthur Mar 25 '16 at 12:58 — Tristan Arthur, Mar 25 '16 at 12:58

user3629249 · Answer 2 · 2016-03-25T19:41:55.983

I needed more room than a comment, so placed it here:

regarding this code:

for (a = 0; a < setLength; a++)
{
    /* This will give the 2nd value. 
     * Resulting in combos with a length of 2 
     */
    for (b = 0; b < setLength; b++)
    {
        printf("%c%c : ", set[a], set[b]);
    }
}

will result in incorrect output combos like:

aa
bb
cc
dd

which are not valid combos

this code:

/* 1st value */
for (a = 0; a < setLength; a++)
{
    /* 2nd value */
    for (b = 0; b < setLength; b++)
    {
        /* 3rd value */
        for (c = 0; c < setLength; c++)
        {
            printf("%c%c%c : ", set[a], set[b], set[c]);
        }
    }
}

will result in output combos like:

aaa
aab
aac
aad
...

which are not valid combos.

On a related subject.

Most of the online code judge questions have severe time limits. Calling `printf() takes a LOT of time.

suggest, when possible to use functions like:

#include <stdio.h>


    void fastRead( size_t *a );
    void fastWrite( size_t a );

    inline void fastRead(size_t *a)
    {
        int c=0;
        // note: 32 is space character
        while (c<33) c=getchar_unlocked();

        // initialize result value
        *a=0;

        // punctuation parens, etc are show stoppers
        while (c>47 && c<58)
        {
            *a = (*a)*10 + (size_t)(c-48);
            c=getchar_unlocked();
        }
        //printf( "%s, value: %lu\n", __func__, *a );
    } // end function: fastRead


    inline void fastWrite(size_t a)
    {
        char snum[20];
        //printf( "%s, %lu\n", __func__, a );

        int i=0;
        do
        {
            // 48 is numeric character 0
            snum[i++] = (char)((a%10)+(size_t)48);
            a=a/10;
        }while(a>0);

        i=i-1; // correction for overincrement from prior 'while' loop

        while(i>=0)
        {
            putchar_unlocked(snum[i--]);
        }
        putchar_unlocked('\n');
    } // end function: fastWrite

More efficient way of listing combinations

2 Answers2