Creating groups based on previous data

Question

I am trying to get my app to determine the best solution for grouping 20 golfers into foursomes.

I have data that shows when a golfer played, what date and the others in the group.

I would like the groups made up of golfer who haven't played together, or when everyone has played together, the longest amount of time that they played together. In other words, I want groups made up of players who haven't played together in a while as opposed to last time out.

Creating a permutation list of 20! to determine the lowest combinations didn't work well.

Is there another solution that I am not thinking of?

Answer 1

@Salix-alba's answer is spot on to get you started. Basically, you need a way to figure out how much time has already been spent together by members of your golfing group. I'll assume for illustration that you have a method to determine how much time two golfers have spent together. The algorithm can then be summed up as:

1. Compute total time spent together of every group of 4 golfers (see Salix-alba's answer), storing the results in an ordered fashion.

2. Pick the group of 4 golfers with the least time together as your first group.

3. Continue to pick groups from your ordered list of possible groups such that no member of the next group picked is a member of any prior group picked

4. Halt when all golfers have a group, which will always happen before you run out of possible combinations.

By way of quick, not promised to compile example (I wrote it in the answer window directly):

Let's assume you have a method time(a,b) where a and b are the golfer identities, and the result is how much time the two golfers have spent together.

Let's also that assume that we will use a TreeMap> to keep track of "weights" associated with groups, in a sorted manner.

Now, let's construct the weights of our groups using the above assumptions:

TreeMap<Integer,Collection<Integer>> options = new TreeMap<Integer, Collection<Integer>>(); 
for(int i=0;i<17;++i) {
    for(int j=i+1;j<18;++j) {
        for(int k=j+1;k<19;++k) {
            for(int l=k+1;l<20;++l) {
                Integer timeTogether = time(i,j) + time(i,k) + time(i,l) + time(j,k) + time(j,l)+time(k,l);
                Collection<Integer> group = new HashSet<Integer>();
                group.add(i);
                group.add(j);
                group.add(k);
                group.add(l);
                options.put(timeTogether, group);
            }
        }
    }
}
Collection<Integer> golferLeft = new HashSet<Integer>(); // to quickly determine if we should consider a group.
for(int a=0; a < maxGolfers, a++) {
    golferLeft.add(a);
}

Collection<Collection<Integer>> finalPicks = new ArrayList<Collection<Integer>>();
do{
    Map.Entry<Integer, Collection<Integer>> least = options.pollFirstEntry();
    if (least != null && golferLeft.containsAll(least.getValue()) {
        finalPicks.add(least.getValue());
        golferLeft.removeAll(least.getValue());
    }
}while (golferLeft.size() > 0 && least != null);

And at the end of the final loop, finalPicks will have a number of collections, with each collection representing a play-group.

Obviously, you can tweak the weight function to get different results -- say you would rather be concerned with minimizing the time since members of the group played together. In that case, instead of using play time, sum up time since last game for each member of the group with some arbitrarily large but reasonable value to indicate if they have never played, and instead of finding the least group, find the largest. And so on.

I hope this has been a helpful primer!

Answer 2

There should be 20 C 4 possible groupings which is 4845. It should be possible to generate these combinations quite easily with four nested for loops.

int count = 0;
for(int i=0;i<17;++i) {
    for(int j=i+1;j<18;++j) {
        for(int k=j+1;k<19;++k) {
            for(int l=k+1;l<20;++l) {
                System.out.println(""+i+"\t"+j+"\t"+k+"\t"+l);
                ++count;
            }
        }
    }
}
System.out.println("Count "+count);

You can quickly loop through all of these and use some objective function to workout which is the most optimal grouping. Your problem definition is a little fuzzy so I'm not sure how tell which is the best combination.

Thats just the number of way picking four golfers out of 20, you really need 5 group of 4 which I think is 20C4 * 16C4 * 12C4 * 8C4 which is 305,540,235,000. This is still in the realm of exhaustive computation though you might need to wait a few minutes.

Another approach might be a probabilistic approach. Just pick the groups at random, rejecting illegal combinations and those which don't meet your criteria. Keep picking random groups until you have found which is good enough.