列出组合的更有效方法

debugcn 发表于 Dev

特里斯坦·阿瑟（Tristan Arthur）

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

#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＃等语言的内置函数。因此，我的问题是：我的回答方式是正确的还是可靠的；如果没有，那么没有内置功能的方法将是一种更有效的方法。

助力车

您可以将简单算法与回溯结合使用-一种技术，可让您使用先前计算的一部分来获取更多值。

这是代码：

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

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

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。