查找给定数字集的所有组合

Question

说我有一组数字'0','1','2',......,'9'.我想找到所有数字,其中只包含我的集合中每个数字中的一个.

问题是:在我开始我的程序之前,我不知道我的设置将包括多少个数字和数字.(例如,该集合可以包含数字'1','3'和'14'.)

我搜索了互联网,偶然发现了"动态编程"这个术语,这个术语显然是用来解决像我这样的问题,但我不明白这些例子.

有人能给我一个如何解决这个问题的提示(可能是动态编程)吗？

编辑:当集合包括像'14'这样的数字时,集合的不同数量当然必须通过某种方式分开,例如当集合包括数字'1','3'和'14'时,组合可以是1-3-14或3-14-1(=由' - '字符分隔的个别数字).

编辑2:这里描述了一个似乎有点类似的问题:其中一个解决方案使用动态编程.

Answer 1

对我来说,看起来你正在寻找一组给定元素的所有排列.

如果您使用C++,则有一个标准函数next_permutation()可以完全满足您的需求.您从排序的数组开始,然后next_permutation重复调用.

示例如下:http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 2

为了在事先不知道必须有多少位输出的情况下检查所有组合，我曾经编写过以下代码：

#include <stdio.h>
#include <stdlib.h>

#define ARRSIZE(arr)    (sizeof(arr)/sizeof(*(arr)))

int main()
{
    const char values[]= {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    char * buffer=NULL;
    int * stack=NULL;
    int combinationLength=-1;
    int valuesNumber=-1;
    int curPos=0;
    fprintf(stderr, "%s", "Length of a combination: ");
    if(scanf("%d", &combinationLength)!=1 || combinationLength<1)
    {
        fputs("Invalid value.\n",stderr);
        return 1;
    }
    fprintf(stderr, "%s (%lu max): ", "Possible digit values",(long unsigned)ARRSIZE(values));
    if(scanf("%d", &valuesNumber)!=1 || valuesNumber<1 || (size_t)valuesNumber>ARRSIZE(values))
    {
        fputs("Invalid value.\n", stderr);
        return 1;
    }
    buffer=(char *)malloc(combinationLength);
    stack=(int *)malloc(combinationLength*sizeof(*stack));
    if(buffer==NULL || stack==NULL)
    {
        fputs("Cannot allocate memory.\n", stderr);
        free(buffer);
        free(stack);
        return 2;
    }
    /* Combinations generator */
    for(;;)
    {
        /* If we reached the last digit symbol... */
        if(stack[curPos]==valuesNumber)
        {
            /* ...get back to the previous position, if we finished exit */
            if(--curPos==-1)
                break;
            /* Repeat this check */
            continue;
        }
        buffer[curPos]=values[stack[curPos]];
        /* If we are in the most inner fake-cycle write the combination */
        if(curPos==combinationLength-1)
            puts(buffer);
        stack[curPos]++;
        /* If we aren't on the last position, start working on the next one */
        if(curPos<combinationLength-1)
        {
            curPos++;
            stack[curPos]=0;
        }
    }
    /* Cleanup */
    free(buffer);
    free(stack);
    return 0;    
}

它只在一个周期内完成所有操作，以避免递归和函数调用开销，即使使用堆栈数组“伪造”所需的嵌套 for 循环。
它的性能相当好，在我的 4 年前的 Athlon64 3800+ 上，需要 2'4" 的用户时间（=> 实际计算时间）来生成 36^6=2176782336 个组合，因此它每秒计算大约 1750 万个组合。

matteo@teoubuntu:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
matteo@teoubuntu:~/cpp$ time ./combinations.x > /media/Dati/combinations.txt
Length of a combination: 6
Possible digit values (36 max): 36

real    13m6.685s
user    2m3.900s
sys 0m53.930s
matteo@teoubuntu:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
matteo@teoubuntu:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
matteo@teoubuntu:~/cpp$ ls -lh /media/Dati/combinations.txt 
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
matteo@teoubuntu:~/cpp$ 

“真实”时间相当长，因为我同时还在电脑上做其他事情。