Parallelisierung der Kombination

Question

Ich habe ein Stück Code, der die Kombination von M Nummer Aus N (nCm) druckt;

Da es eine Rekursion ist, arbeitet es sehr langsam, wenn N groß ist.

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

Ich würde gerne wissen, ob es im obigen Algorithmus noch Raum für Verbesserungen gibt? Wenn möglich, kann ich openMP verwenden?

Dank

Answer 1

Für mich war der Code selbst die gewünschte Ausgabe zu geben. see

Ich habe mich verändert

1. Druckformat jede Kombination war nicht gut genug.
2. wiederholte Kombinationen. (Hinweis: sonst Teil der if-Anweisung hinzugefügt).
3. reduziert 2 rekursiven Aufruf mit einer Schleife und einem rekursiven Aufruf. (Weniger Platz.)

Der erforderliche Code lautet:

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