算法，从n个元素的列表中寻找组合

Question

我想编写一个函数来从n元素的列表中选择k元素的组合。我有我以pdf格式转换为文本的给定源文件。并且我得到了以下列表。我试图使用dfs找到组合，但有约束，需要先管理，它令我困惑。我们需要从下面的列表中选择3个主题。在下面的行/意味着这些科目中的任何一个，如Ex.from a)History or Sociology or Economics应该被选中。约束条件是数学不能与孟加拉语或印地语任何组合。 一些有效的组合是

        History,Bengali,Sanskrit 
           Bengali,Philosophy,English 

列表的快照 -

a) History/Sociology/Economics 
b) Bengali/Hindi 
c) Sanskrit/Mathematics 
d) Philosophy 
e) Political Science 
f) English 

共有3科目组合会像(6C3*3*2*2)-24（从我的计算） 我想到了一个办法来表示列表，以便我可以有效地编码它。但不能找出一个合理的方法来解决这个问题。 这是我实现

#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
int counter=0; 
void combination(char *p[10],char *d[10],int start,int end,int index,int r){ 
    int i,j,k=0; 
// char ch[10]="History"; 
    if(index==r){ 

    if(!strcmp(d[0],"History")){ 
     if(!strcmp(d[1],"Sociology") || !strcmp(d[1],"Economics") || !strcmp(d[2],"Sociology") || !strcmp(d[2],"Economics")) 
       return; 
     } 
    if(!strcmp(d[0],"Sociology")){ 
     if(!strcmp(d[1],"History") || !strcmp(d[1],"Economics") || !strcmp(d[2],"History") || !strcmp(d[2],"Economics")) 
       return; 
     } 
    if(!strcmp(d[0],"Economics")){ 
     if(!strcmp(d[1],"History") || !strcmp(d[1],"Sociology") || !strcmp(d[2],"History") || !strcmp(d[2],"Sociology")) 
       return; 
       } 
    if(!strcmp(d[0],"Bengali")){ 
     if(!strcmp(d[1],"Hindi") || !strcmp(d[2],"Hindi") || !strcmp(d[1],"Mathematics") || !strcmp(d[2],"Mathematics")) 
       return; 
       } 
    if(!strcmp(d[0],"Hindi")){ 
     if(!strcmp(d[1],"Bengali") || !strcmp(d[2],"Bengali") || !strcmp(d[1],"Mathematics") || !strcmp(d[2],"Mathematics")) 
       return; 
       } 
    if(!strcmp(d[0],"Sanskrit")){ 
     if(!strcmp(d[1],"Mathematics") || !strcmp(d[2],"Mathematics")) 
       return; 
       } 
    if(!strcmp(d[0],"Mathematics")){ 
     if(!strcmp(d[1],"Sanskrit") || !strcmp(d[2],"Sanskrit") || !strcmp(d[1],"Bengali") || !strcmp(d[2],"Bengali") || !strcmp(d[1],"Hindi") || !strcmp(d[2],"Hindi")) 
       return; 
       } 
    if(!strcmp(d[1],"Mathematics")){ 
     if(!strcmp(d[2],"Bengali") || !strcmp(d[2],"Hindi")) 
     return; 
     } 
    if(!strcmp(d[2],"Mathematics")){ 
       if(!strcmp(d[1],"Bengali") || !strcmp(d[1],"Hindi")) 
       return; 
       } 

    for(j=0;j<r;j++) 
    printf("%s ",d[j]); 
    counter++; 
    printf("\n"); 
    return; 
    } 
    for(i=start;i<=end && end-i+1>=r-index; i++){ 
    d[index]=p[i]; 
    combination(p,d,i+1,end,index+1,r); 
    } 
     } 
int main(){ 
    char *subject[10],n[50],*p,*data[10]; 
    int len,i,m; 
    printf("\nEnter the no subject\n"); 
    scanf("%d",&m); 
    printf("\nEnter name of subject\n"); 
    for(i=0;i<m;i++){ 
    scanf("%s",n); 
    len=strlen(n); 
    p=(char *)malloc(len+1); 
    strcpy(p,n); 
    subject[i]=p; 
    } 
    combination(subject,data,0,m-1,0,3); 
    printf("\nCount=%d\n",counter); 
    return 0; 
    } 

如果什么列表是挺大那么如何处理其输出会更加大，那么复杂性将增加，最终会失败 有没有解决这个任何优雅的方式与任何语言的预定义的语言数据结构

Answer 1

这里有一个建议：组织您的数据，以便它是一个列表的列表：主列表代表的组，子列表代表每个组的主题。

subjects = [ 
    ["History", "Sociology", "Economics"], 
    ["Bengali", "Hindi"], 
    ["Sanskrit", "Mathematics"], 
    ["Philosophy"], 
    ["Political Science"], 
    ["English"] 
] 

然后继续在三个嵌套步骤：

• 首先，生成基团，例如所有的3项的组合'{a，b，e}'。您可以look for a good algorithm on SO或自己推出。考虑到你的组很小，你可以遍历从0到63的整数，并考虑所有设置了三位的数字。当设置位j时，组合中包含组j。

• 现在你有一个三组的列表。在这些列表中构建Cartesian product的主题。既然你正在处理三个列表，这应该只是一个三重嵌套循环。

• 现在你有三个主题。这些科目可能会违反剩下的一个限制条件，即你不能同时拥有数学和孟加拉语或印地语。手动检查此约束并将主题组合添加到您的集合中。

对于它的价值，这里有一个快速和肮脏的实施，C，这将在C++编译：

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

#define SUBJECT(X)           \ 
    X(History) X(Sociology) X(Economics) X(Bengali)   \ 
    X(Hindi) X(Sanskrit) X(Mathematics) X(Philosophy)  \ 
    X(PolScience) X(English) 

#define ENUM(X) X, 
#define STR(X) #X, 

enum {SUBJECT(ENUM) None = -1}; 
const char *subject[] = {SUBJECT(STR) NULL}; 

int has(int *grp, int sub) 
{ 
    if (*grp++ == sub) return 1; 
    if (*grp++ == sub) return 1; 
    if (*grp++ == sub) return 1; 

    return 0; 
} 

int main() 
{ 
    int choice[6][4] = { 
     {History, Sociology, Economics, None}, 
     {Bengali, Hindi, None}, 
     {Sanskrit, Mathematics, None}, 
     {Philosophy, None}, 
     {PolScience, None}, 
     {English, None}, 
    }; 
    int i; 

    for (i = 0; i < 64; i++) { 
     int *grp[6]; 
     int n = 0; 
     int k, l, m; 

     for (m = 0; m < 6; m++) { 
      if (i & (1 << m)) grp[n++] = choice[m]; 
     } 

     if (n != 3) continue; 

     for (k = 0; grp[0][k] != None; k++) { 
      for (l = 0; grp[1][l] != None; l++) { 
       for (m = 0; grp[2][m] != None; m++) { 
        int sub[3] = {grp[0][k], grp[1][l], grp[2][m]}; 

        if (has(sub, Mathematics) 
        && (has(sub, Hindi) || has(sub, Bengali))) continue; 

        printf("%s, %s, %s\n", subject[sub[0]], 
         subject[sub[1]], subject[sub[2]]); 
       } 
      } 
     }   
    } 

    return 0; 
}