算法，从具有 n 个元素的列表中查找组合

Question

我想为 select n 列表中的 k 个元素的组合编写一个函数 element.I 具有我在 text.And 中转换的 pdf 格式的给定源文件我得到了以下列表。我试图使用 dfs 来查找组合，但首先需要管理约束，这令人困惑 me.Say 我们需要从以下列表中 select 3 个主题。在接下来的几行中，/ 表示这些科目中的任何一门，例如 Ex.from a)History or Sociology or Economics 应该是 selected.The 约束是数学不能与孟加拉语或印地语结合使用。一些有效的组合是

                                 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。由于您只处理三个列表，因此这应该只是一个三重嵌套循环。
现在你有三个主题。这些科目可能会违反剩下的唯一限制，即您不能同时拥有数学和孟加拉语或印地语之一。手动检查此约束并将主题组合添加到您的 collection.

为了它的价值，这里有一个用 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;
}

算法，从具有 n 个元素的列表中查找组合

Algorithm ,Finding combination from a list with n elements

c

python

java

algorithm

combinations