# 算法以匹配最可能的组合

go评论68阅读模式

Algorithm to match most possible combinations

# 问题

``````// 限制：不智能。示例：大小为7，队伍2,2,4,3,1,5 -> 2,5和4,3可以匹配，但会选择2,2,3和4,1,5
// 可能的解决方案：按大小排序，或者将团队与可能的最低匹配匹配，例如尝试5,1然后是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();
}

// 遍历所有团队并将匹配的团队添加到两个队伍
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))) {
} else if (team2.stream().mapToLong(c -> c.getMembers().size()).sum() + parties.get(i).getMembers().size() <= teamSize
&& !team1.contains(parties.get(i))) {
}
}

// 当第一个队伍已满时重置搜索
if ((team1.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize
|| team2.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize) && !teamReset) {
counter = 0;
teamReset = true;
}

// 检查是否遍历了所有团队，如果是，则退出循环
if (counter <= parties.size()) {
counter++;
} else {
break;
}
}

// 是否仍然找到了队伍？如果没有，返回大厅
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);
parties.removeAll(team1);
parties.removeAll(team2);
} else {
return lobbies;
}
}

// 如果所有团队都找到了队伍，也返回
return lobbies;
}
``````

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 -&gt; 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&lt;MatchedParty&gt; getLobbies(List&lt;Party&gt; parties, int teamSize) {
List&lt;MatchedParty&gt; lobbies = new ArrayList&lt;&gt;();
parties.sort(Comparator.comparing(Party::getJoinedQueueTime));
while (!(parties.isEmpty())) {
MatchedParty matchedParty = new MatchedParty();
List&lt;Party&gt; team1 = new ArrayList&lt;&gt;();
List&lt;Party&gt; team2 = new ArrayList&lt;&gt;();
boolean teamReset = false;
int counter = 0;
while (team1.stream().mapToLong(c -&gt; c.getMembers().size()).sum() != teamSize || team2.stream().mapToLong(c -&gt; c.getMembers().size()).sum() != teamSize) {
if (team1.stream().mapToLong(c -&gt; c.getMembers().size()).sum() != teamSize) {
team1.clear();
}
if (team2.stream().mapToLong(c -&gt; c.getMembers().size()).sum() != teamSize) {
team2.clear();
}
// Iterate over all parties and add matching ones to the teams
for (int i = counter; i &lt; parties.size(); i++) {
if (team1.stream().mapToLong(c -&gt; c.getMembers().size()).sum() + parties.get(i).getMembers().size() &lt;= teamSize &amp;&amp; !(team2.contains(parties.get(i)))) {
} else if (team2.stream().mapToLong(c -&gt; c.getMembers().size()).sum() + parties.get(i).getMembers().size() &lt;= teamSize &amp;&amp; !(team1.contains(parties.get(i)))) {
}
}
// Reset search when first team is full
if ((team1.stream().mapToLong(c -&gt; c.getMembers().size()).sum() == teamSize || team2.stream().mapToLong(c -&gt; c.getMembers().size()).sum() == teamSize) &amp;&amp; !(teamReset)) {
counter = 0;
teamReset = true;
}
// Check if we iterated over all parties, if so exit the loop
if (counter &lt;= parties.size()) {
counter++;
} else {
break;
}
}
// Are there still teams found? If not, return the lobbies
if (team1.stream().mapToLong(c -&gt; c.getMembers().size()).sum() == teamSize &amp;&amp; team2.stream().mapToLong(c -&gt; c.getMembers().size()).sum() == teamSize) {
matchedParty.setTeam1(team1);
matchedParty.setTeam2(team2);
parties.removeAll(team1);
parties.removeAll(team2);
} else {
return lobbies;
}
}
return lobbies;
}
``````

# 答案1

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

``````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)
{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}
``````

``````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)
``````

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

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Partitions/partitions.html#pcalc1

``````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)
``````

``````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,

<details>
<summary>英文:</summary>

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 &lt; 8`, so you can&#39;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&#39;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.
</details>
# 答案2
**得分**: 0

<details>
<summary>英文:</summary>
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.
</details>
``````

• 本文由 发表于 2020年10月8日 10:24:44
• 转载请务必保留本文链接：https://go.coder-hub.com/64254903.html
• algorithm
• combinations
• java
• matchmaking
• math

go 132

go 61

go 71

go 61