列出组合的更有效方式

Question

最近我回答了很多重复的问题之一“如何获取在此处插入数据类型的数组的所有可能组合。我的回答是：

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

然而，当我查看这个问题的其他答案时，它们都涉及该语言的内置函数，例如C＃。因此，我的问题是：我回答的方式是否正确或可靠，如果不是，那么在没有内置功能的情况下，什么是更有效的方式。

Answer 1

您可以使用带有回溯的简单算法 - 一种允许您使用之前计算的一部分来获得更多值的技术。

代码如下：

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] = '[=10=]';
    print_comb_rec(values, n, length, helper);

    free(helper);
}

用法：使用函数print_comb。它需要值来排列，数组的长度 n 和组合的长度。通过使用它，您可以获得给定长度的结果。

请注意，对于给定的 n，可能组合的数量呈指数增长（即 O(n^length)）。对于任何递归算法，也有可能运行使用它超出堆栈内存。

Answer 2

我需要比评论更多的空间，所以把它放在这里：

关于此代码：

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

将导致不正确的输出组合，例如：

aa
bb
cc
dd

这不是有效的组合

此代码：

/* 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]);
        }
    }
}

将产生如下输出组合：

aaa
aab
aac
aad
...

这不是有效的组合。

关于相关主题。

大多数在线代码判断题都有严格的时间限制。调用 `printf() 需要很多时间。

建议尽可能使用如下函数：

#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

c

combinations

loops