Algorithm ,Finding combination from a list with n elements

Question

I want to write a function to select combination of k element from list of n element.I have the given source file in pdf form that i converted in text.And i got the following list .I was trying to use dfs to find the combinations but there are constraint that need to be managed first, its confusing me.Say we need to select 3 subjects from the following list. In the following lines / means any one of these subjects,like for Ex.from a)History or Sociology or Economicsshould be selected.The constraint's are that Mathematics Can't be in any combination with Bengali or Hindi. Some valid combination are

                                 History,Bengali,Sanskrit
                                 Bengali,Philosophy,English

The snapshot of the list -

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

Total 3 subject combination will be something like (6C3*3*2*2)-24(from my calculation) I am thinking a way to represent the list so that i can code it efficiently .But can't figure out a reasonable way to solve this . Here is my implementation

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

What if the list is getting bigger then how to handle the output it will be much large then complexity will be increase and eventually it will fail Is there any elegant way to solve this with predefined language data structure in any language

The solution will be very different depending on language. Please pick one, I recommend the one you have written your attempt in. You *have* attempted to solve it yourself? — Some programmer dude, Apr 24 '15 at 09:50
1) which language? 2) what have you tried so far? We don't do homeworks here. — holgac, Apr 24 '15 at 09:50
this is from a project i am working on that have a list like this and i have to check it if its a valid selection option based on total possible combinations from the list @holgac — Xax, Apr 24 '15 at 09:55
Well, DFS would probably work. Check constraints at each depth and at depth 3, you'll have the combination you require. If you write a similar code and still have problems, we can help more. — holgac, Apr 24 '15 at 10:00
@JoachimPileborg Why will the solution depend so much on language? The OP asked for an algorithm, not for code. Asking him/her to specify a language makes no sense. — Dawood ibn Kareem, Apr 24 '15 at 10:01
Do you want to test whether a certain three-subject combination is valid or do you want to generate all valid combinations? — M Oehm, Apr 24 '15 at 10:07
@holgac i dont need code i need way to look at this problem to solve — Xax, Apr 24 '15 at 10:07

score 1 · Accepted Answer · edited May 23 '17 at 11:43

Here's a suggestion: Organise your data so that it is a list of lists: The main list represents the groups, the sublists represent the subjects in each group.

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

Then proceed in three nested steps:

First, generate all 3-item combinations of groups, e.g. ' {a, b, e}'. You can look for a good algorithm on SO or roll your own. Given that your set of groups is small, you can just iterate through the integers from 0 to 63 and consider all numbers that have exactly three bits set. When bit j is set, group j is included in the combo.
Now you have a list of three groups. Build the Cartesian product of the subjects in these lists. Since you are dealing with eactly three lists, this should be just a triple nested loop.
Now you have three subjects. These subjects might violate the single remaining constraint that you cannot have both Mathematics and one of Bengali or Hindi in your combination. Check this constraint manually and add the subject combo to your collection.

For what it's worth, here's a quick and dirty implementation in C, which will compile in 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;
}

Algorithm ,Finding combination from a list with n elements

1 Answers1