Algorithm to match most possible combinations

Question

I'm currently struggling to write an algorithm for my matchmaking system. It's probably childsplay for people who know anything about maths, well, I do not.

Let's take the following example:

A lobby consists of exactly 8 players.
There are 9 parties in the queue. The party sizes are: 1, 6, 3, 8, 2, 1, 5, 3, 2.
The algorithm needs to create as many full lobbies as possible out of those parties.

There may only be full lobbies. So there might be parties that cannot be matched. Those will then wait for new parties to come in the queue.

My current code does match the parties to lobbies, but it lacks the functionality to find the best combinations to find the most possible amount of full lobbies.

Example: Lobby Size of exactly 7, Parties: 2,2,4,3,1,5 -> 2,5 and 4,3 could be matched, but it will do 2,2,3 and 4,1,5 cannot be matched.

I do appreciate any help.

My current code:

    // Limitation: Is not intelligent. Example: Size 7, Teams 2,2,4,3,1,5 -> 2,5 and 4,3 could be matched, but it will do 2,2,3 and 4,1,5
    // Possible solution: Sort for size or match parties with lowest possible match e.g try 5,1 then 5,2 ...
    public List<MatchedParty> getLobbies(List<Party> parties, int teamSize) {
        List<MatchedParty> lobbies = new ArrayList<>();

        parties.sort(Comparator.comparing(Party::getJoinedQueueTime));

        while (!(parties.isEmpty())) {
            MatchedParty matchedParty = new MatchedParty();
            List<Party> team1 = new ArrayList<>();
            List<Party> team2 = new ArrayList<>();

            boolean teamReset = false;
            int counter = 0;
            while (team1.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize || team2.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {

                if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {
                    team1.clear();
                }

                if (team2.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {
                    team2.clear();
                }

                // Iterate over all parties and add matching ones to the teams
                for (int i = counter; i < parties.size(); i++) {
                    if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() + parties.get(i).getMembers().size() <= teamSize && !(team2.contains(parties.get(i)))) {
                        team1.add(parties.get(i));
                    } else if (team2.stream().mapToLong(c -> c.getMembers().size()).sum() + parties.get(i).getMembers().size() <= teamSize && !(team1.contains(parties.get(i)))) {
                        team2.add(parties.get(i));
                    }
                }

                // Reset search when first team is full
                if ((team1.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize || team2.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize) && !(teamReset)) {
                    counter = 0;
                    teamReset = true;
                }

                // Check if we iterated over all parties, if so exit the loop
                if (counter <= parties.size()) {
                    counter++;
                } else {
                    break;
                }
            }

            // Are there still teams found? If not, return the lobbies
            if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize && team2.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize) {
                matchedParty.setTeam1(team1);
                matchedParty.setTeam2(team2);
                lobbies.add(matchedParty);
                parties.removeAll(team1);
                parties.removeAll(team2);
            } else {
                return lobbies;
            }
        }

        // Maybe all parties found a team, if so return too
        return lobbies;
    }

Answer 1

Your algorithm is generally right way to go, but there is one improvement you can do. Since you only care about make exact matches of a given party size, I would map each party to a list that contains all parties of a given size: IE: {1: [parties of size 1], 2: [parties of size 2], ...}

Then take a look at this:

https://en.wikipedia.org/wiki/Partition_%28number_theory%29

The tricky bit is we want to match things as ideally as possible. Basically we want to start with the least number of parties to most number of parties that need to be combined. IE for party size of 8: 8, 7 + 1, 6 + 2, 5 + 3 and so on. Once those have all been matched then we look at the ones that require combining 3 parties (always in order of most to least): 6 + 1 + 1, 5 + 2 + 1, 4 + 2 + 2... then the ones with 4 parts, then 5 parts, 6 parts, 7 parts, and lastly 8 parts (all ones).

Looks like there are 22 partitions of 8, you could likely just hard code them and loop over them. Depending on your max number of parties, you could build a partitions table for all number of parties you need.

This is roughly how that algorithm would work on your example list:

1, 6, 3, 8, 2, 1, 5, 3, 2

{party size: number of parties remaining}
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{6: 1, 5: 1, 3: 2, 2: 2, 1: 1} => (8)
{5: 1, 3: 2, 2: 1, 1: 1} => (8), (6,2)
{3: 1, 2: 1, 1: 1} => (8), (6,2), (5,3)
{3: 1, 2: 1, 1: 1}

If you keep an eye on the total of the remaining parties you would stop checking there are 3 + 2 + 1 = 6 < 8, so you can't create any additional valid parties. I believe this creates the idea number of parties.

Example where you aimed to have party of 7:

2,2,4,3,1,5
{5: 1, 4: 1, 3: 1, 2: 2}
{4: 1, 3: 1, 2: 1} => (5,2),
{2: 1} => (5,2),(4,3)

Again at this point, it's impossible to make a party of 7.

As for generating partitions, this seems solid:

https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/

Whether you need to optimize or not depends on max party size. 16 has 231 partitions, but 32 has 8349 still not bad, but 64 has 1741630, that could be bad unless you have a lot of parties. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Partitions/partitions.html#pcalc1

Edit: Only problem here is that small parties may be disadvantaged. In this case, you may reverse the search order, so it starts looking at parties of min size (all ones) instead of min size (full party). I would probably reverse the search order every say 3-10 party searches. Depending on how often you do it.

You might also want to try doing both directions, then just picking the one with the better results.

In reverse order:

1, 6, 3, 8, 2, 1, 5, 3, 2
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{8: 1, 6: 1, 5: 1, 3: 1} => (1,2,2,3)
{6: 1} => (1,2,2,3),(3,5),(8)

While in this case, both ways created 3 full groups, I doubt this will always be the case. However, notice this approach did reduce it down to only 1 party of 6, instead of a party of 3, 2 and 1.

This approach basically seeks to reduce the number of parties as much as possible. The other approach aims to maximize the number of full groups. Both have their uses and recommend you use both, just a question of how often you use one vs the other.

Hmmm a 3rd option might to attack it from both sides, though in this case, you have other issues, with it being biased against those in the middle.

1, 6, 3, 8, 2, 1, 5, 3, 2
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{6: 1, 5: 1, 3: 2, 2: 2, 1: 1} => (8)
{6: 1, 5: 1, 3: 1} => (8),(1,2,2,3)
{6: 1} => (8),(1,2,2,3),(5,3)

Really, you could randomly shuffle all of the partitions and run the algorithm that way too if you want to make things more interesting, though doubt that would yield above average results. Main point is that integer partitions of N are what you need to be looking at.

Answer 2

So, after reading through the several links from commenters, it seems like the answer from @Andreas is the most correct one. It seems like my problem is a variant of the bin packing problem, just that in my case I do have the requirement to have only filled bins.

My issue could mostly be solved by using the algorithm I already posted in the question, but sorting all entries from highest to lowest and when filling the lobbies (bins), insert the biggest entries first.