java - 算法，从包含 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;
}