匹配大多数可能组合的算法

Question

我目前正在努力为我的配对系统编写算法。对于懂数学的人来说，这可能是儿戏，嗯，我不懂。

举个例子：

一个大厅由正好 8 名玩家组成。
队列中有 9 方。聚会人数为：1、6、3、8、2、1、5、3、2。
该算法需要从这些派对中创建尽可能多的完整游说团体。

可能只有完整的大厅。所以可能会有无法配对的派对。然后他们将等待新的派对进入队列。

我当前的代码确实将各方与大厅相匹配，但它缺少找到最佳组合以找到尽可能多的完整大厅的功能。

示例：大厅大小刚好为 7，派对：2,2,4,3,1,5 -> 2,5 和 4,3 可以匹配，但它会匹配 2,2,3 和 4 ,1,5 无法匹配。

非常感谢任何帮助。

我当前的代码：

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

因此，在阅读了评论者提供的几个链接后，@Andreas 的回答似乎是最正确的。看来我的问题是装箱问题的一个变体，只是在我的情况下，我确实要求只装满箱子。

我的问题大部分可以通过使用我已经在问题中发布的算法来解决，但是将所有条目从最高到最低排序，并且在填充大厅（垃圾箱）时，首先插入最大的条目。

Answer 2

您的算法通常是正确的方法，但您可以做一项改进。由于您只关心给定派对人数的精确匹配，我会将每个派对映射到包含给定人数的所有派对的列表：即：{1: [parties of size 1], 2: [parties of size 2], ...}

再看看这个：

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

棘手的一点是我们希望尽可能完美地匹配事物。基本上，我们希望从最少的参与方开始，到需要合并的最多参与方。 8 人聚会的 IE：8, 7 + 1, 6 + 2, 5 + 3 等等。一旦所有这些都匹配，我们就会查看需要组合 3 个部分的那些（总是按照从多到少的顺序）：6 + 1 + 1, 5 + 2 + 1, 4 + 2 + 2... 然后是 4 个部分，然后是 5 个部分、6 个部分、7 个部分，然后最后 8 个部分（全部）。

看起来有 22 个分区，每分区 8 个，您可能只需对它们进行硬编码并对其进行循环。根据您的最大派对数量，您可以为您需要的所有派对数量构建分区 table。

这就是该算法在您的示例列表中的大致工作方式：

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}

如果您关注剩余派对的总数，您将停止检查是否有 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

编辑：这里唯一的问题是小政党可能处于不利地位。在这种情况下，您可以颠倒搜索顺序，因此它会开始查找最小大小的聚会（全部）而不是最小大小（完整聚会）。我可能会在每次搜索 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 人的 1 方，而不是 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, 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)

真的，如果你想让事情变得更有趣，你可以随机打乱所有分区和运行算法，尽管怀疑这会产生高于平均水平的结果。要点是 N 的整数分区是您需要查看的内容。

匹配大多数可能组合的算法

Algorithm to match most possible combinations

java

algorithm

math

combinations

matchmaking