找到一个给定的组号码的所有组合 [英] Find all combinations of a given set of numbers

问题描述

说我有一组数字0，1，2，...，9。我想找到包含在我的设置完全相同的每一个号码中的一个所有数字。

say I have a set of numbers '0', '1', '2', ..., '9'. I want to find all numbers that contain exactly one of each of the numbers in my set.

现在的问题是：在我开始我的计划，我不知道我会集了多少数量和哪些号码包括。 （例如，所述集可包括数字'1'，'3'和'14'）。

The problem is: Before I start my program, I do not know how many numbers and which numbers my set will include. (For example, the set could include the numbers '1', '3' and '14'.)

我在网上搜索，并偶然发现了术语动态规划，这显然是值得用来解决像我一样的问题，但我不明白的例子。

I searched the internet, and stumbled upon the term 'dynamic programming' which apparently is something to use to solve problems like mine, but I did not understand the examples.

有人可以给我如何解决这个问题（可能与动态规划）？

Can somebody give me a hint on how to solve this problem (possibly with dynamic programming)?

编辑：当集包括象'14'的不同数目的组当然会被用某种手段，例如，分隔的数字当集包括数字'1'，'3'，和'14'，组合可以是像1-3-14或3-14-1（由一个'-'-字符分隔=个人数字）。

When the set includes numbers like '14' the different numbers of the set would of course have to be separated by some means, e.g. when the set includes the numbers '1', '3', and '14', combinations could be something like 1-3-14 or 3-14-1 (= individual numbers separated by a '-'-character).

编辑2：有一个问题，这似乎是有点类似被描述这里：解决方案之一是使用动态规划

EDIT 2: One problem that seems to be somewhat similar is described here: one of the solutions uses dynamic programming.

推荐答案

要检查所有的组合，而无需事先知道有多少位必须有输出，有一次我写了这个code：

To examine all the combinations without knowing in advance how many digits must have the output, I once wrote this code:

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

它做的一切只是在一个周期内，以避免递归和函数调用的开销，如果还是赝品的嵌套使用堆叠阵列循环需要。
它的性能相当不错，在我4岁的Athlon64 3800+它需要24的用户时间（=>实际计算时间）来生成36 ^ 6 = 2176782336组合，因此它每秒计算约17.5万种组合。

It does everything just in one cycle to avoid recursion and function calls overhead, still if "fakes" the needed nested for loops using the stack array.
It performs quite well, on my 4 years old Athlon64 3800+ it takes 2' 4" of user time (=> actual computation time) to generate 36^6=2176782336 combinations, so it computes about 17.5 million combinations per second.

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$ 

真实的时间是相当高的，因为我也做别的事情的PC中同时上。

The "real" time is quite high because I was also doing something else on the PC in the meanwhile.

这篇关于找到一个给定的组号码的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！