问题

以下是您提供的代码的翻译部分：

// 限制：不智能。示例：大小为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))) {
                    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));
                }
            }

            // 当第一个队伍已满时重置搜索
            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);
            lobbies.add(matchedParty);
            parties.removeAll(team1);
            parties.removeAll(team2);
        } else {
            return lobbies;
        }
    }

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

请注意，由于您要求只返回翻译后的部分，我已经删除了注释和代码块之间的空行。如果您需要原始代码的完整翻译，包括注释和代码块之间的空行，请随时告诉我。

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

答案1

得分: 1

你的算法基本上是正确的，但还有一个改进的空间。因为你只关心给定派对规模的完全匹配，我建议将每个派对映射到一个列表，其中包含所有给定规模的派对：

例如：{1: [大小为1的派对列表], 2: [大小为2的派对列表], ...}

然后看一下这个链接：

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

关键在于，我们希望尽可能地理想地匹配派对。基本上，我们希望从需要组合的派对最少的数量开始，一直到需要组合的派对最多的数量。例如，对于派对大小为8：8, 7 + 1, 6 + 2, 5 + 3等等。一旦这些都被匹配了，我们再看那些需要组合3个派对的情况（始终按照从最多到最少的顺序）：6 + 1 + 1, 5 + 2 + 1, 4 + 2 + 2...，然后是4个派对的情况，5个派对，6个派对，7个派对，最后是8个派对（全部为1）。

看起来有22种将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, 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}

如果你关注剩余派对的总数，你会注意到剩余派对总数是3 + 2 + 1 = 6 < 8，所以无法再创建任何额外的有效派对。我相信这创造了最理想的派对数量。

以目标为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)

在这一点上，无法创建一个大小为7的派对。

关于生成分割，这个链接似乎很不错：

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

是否需要优化取决于最大派对规模。16有231种分割方式，但32有8349种，仍然不错，但64有1741630种，这可能不太好，除非你有很多派对。
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Partitions/partitions.html#pcalc1

编辑：
唯一的问题在于小派对可能会受到不利影响。在这种情况下，你可以颠倒搜索顺序，从最小大小的派对开始搜索（全是1），而不是从最大大小的派对开始。我建议每隔3-10次派对搜索就颠倒一次搜索顺序。具体多久取决于你的选择。

你还可以尝试同时从两个方向进行搜索，然后选择结果更好的那一个。

以颠倒顺序为例：

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)

虽然在这种情况下，两种方法都创建了3个完整的组，但我怀疑这种情况不会总是发生。不过要注意，这种方法确实将大小为6的派对减少为了只有一个，而不是一个大小为3、一个大小为2和一个大小为1的派对。

这种方法基本上旨在尽量减少派对的数量。另一种方法旨在最大化完整组的数量。两种方法都有用途，我建议你同时使用这两种方法，只是根据需要选择其中之一。

嗯，第三种选择可能是从两个方向同时进行攻击，不过在这种情况下，你会遇到其他问题，因为它会偏向中间的情况。

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 < 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.
</details>
# 答案2
**得分**: 0
所以，在阅读了评论者提供的几个链接后，似乎@Andreas的回答是最正确的。看起来我的问题是装箱问题的变体，只是在我的情况下，我确实需要只有已填充的容器。
通过使用我已经在问题中发布的算法，可以基本解决我的问题，但需要将所有条目从高到低排序，并在填充大厅（容器）时优先插入最大的条目。
<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>