Get all distinct combinations of n elements from m sets

I am trying to build an algorithm that selects a combination of 4 horses from multiple races.

So let's say we have 10 races, each with 8 horses: I want all 4 horse combinations to be in those races, assuming 4 horses come from separate races (no horse in one combination can come from the same race).

Is there a name for this problem (and an existing algorithm)?

I'm guessing it will only be a series of loops, but I didn't have my coffee today ... Cheers

EDIT: I have to say that for each combination, I am doing a rather long function in combination, so I don't want to repeat the combinations already executed.

EDIT: is this any better?

            n = number of races;
            for ( int i = 0; i < n; i++ ) {
                for ( int j = i + 1; j < n; j++ ) {
                    for ( int k = j + 1; k < n; k++ ) {
                        for (int l = k + 1; l < n; l++) {
                            //for each combination of 4 separate sets
                            for(int p = 0; p < races.get(i).getHorses().size(); p++){
                                for(int q = 0; q < races.get(j).getHorses().size(); q++){
                                    for(int r = 0; r < races.get(k).getHorses().size(); r++){
                                        for(int s = 0; s < races.get(l).getHorses().size(); s++){
                                            //each combination of 4 horses
                                            races.get(i).getHorses().get(p)
                                            races.get(j).getHorses().get(q)
                                            races.get(k).getHorses().get(r)
                                            races.get(l).getHorses().get(s)
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

      

+3


source to share


2 answers


You basically have two problems. One to choose 4 races out of 10 in total (the order does not matter), which is 10! / (6! * 4!) Or 210 combinations. Then, for each combination of four races, you can choose any of the 8 horses in each race, which is 8 ^ 4 or 4096.



0


source


I'm not very sure, but Chase Twiddle (algorithm) might help fix your problem.



Please check it out: - Phillip J Chase, ` Algorithm 382: Combinations of M of N Objects ' (1970)

+1


source







All Articles