c - 组合并行化

Question

我有一段代码可以打印来自 N (nCm) 的 M 数的组合；

由于是递归，所以当N很大时，速度会很慢。

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

#define N  80
#define M  4

int result[M]= {0}; // THE ARRAY THAT SAVE THE RESULT OF ONE COMBINATION
int queue[N] = {0};
int top = 0;

void comb(int* input,int s, int n, int m)
{
    if (s > n)
        return ; 

    if (top == m)
    {
        for (int i = 0; i < m; i++)
        {
            result[i] = queue[i];
            printf("%d\n", queue[i]);
        }
     }

     queue[top++] = input[s];
     comb(input,s+1, n, M);
     top--;
     comb(input,s+1, n, M);
}

int main()
{  
   int array[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
                  27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,
                  50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,
                  73,74,75,76,77,78,79,80};

    printf("\ncombination():\n");
    comb(array,0, N, M);
    printf("\n");
}

我想知道上面的算法还有没有改进的空间？ 如果可能的话，我可以使用 openMP 吗？

谢谢

Answer 1

对我来说，你的代码甚至给出了所需的输出。 see

我变了

1. 每种组合的打印格式都不够好。
2. 重复组合。 (注:添加了 if 语句的 else 部分)。
3. 通过循环和递归调用减少了 2 次递归调用。 (空间较小。)

所需的代码是:

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

#define N  20
#define M  6

int result[M]= {0}; // THE ARRAY THAT SAVE THE RESULT OF ONE COMBINATION
int queue[N] = {0};
int top = 0;

void comb(int* input,int s, int n, int m)
{
    if (s > n)
        return ; 

    if (top == m)
    {
        printf("\n");
        for (int i = 0; i < m; i++)
        {
            result[i] = queue[i];
            printf("%d ", queue[i]);
        }
     }else{
         for(int ss=s;ss<n;ss++){
            queue[top++] = input[ss];
            comb(input,ss+1, n, m);
            top--;
         }
         //comb(input,s+1, n, m);   
     }
}

int main()
{  
   int array[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
                  27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,
                  50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,
                  73,74,75,76,77,78,79,80};

    printf("\ncombinations():\n");
    comb(array,0, N, M);
    printf("\n");
}