有什么比for循环更好的方法来实现涉及集合的算法？

Question

我正在尝试按以下方式创建算法：

- 创建8个参与者

- 每个参与者都有一系列兴趣

- 与最少兴趣的另一位参与者签订合同

所以我到目前为止所做的是创建2个类，参与者和兴趣，其中兴趣是可以清除的，这样我就可以用它创建一个集合。我手动创建了8个不同名称和兴趣的参与者。

我已经选择了一个参与者数组，并且我使用了一个基本的for循环来使用sets的intersection（）函数将它们组合在一起。不知何故，我的索引总是超出范围，我很肯定有一个更好的方法，但它只是如此凌乱，我不知道从哪里开始。

for i in 0..<participantsSelected.count {
    if participantsSelected[i].interest.intersection(participantsSelected[i+1].interest) == [] {
        participantsSelected.remove(at: i)
        participantsSelected.remove(at: i+1)
        print (participantsSelected.count)
    }
}

所以我的另一个问题是使用这个特定算法的for循环看起来有点过，因为如果它们都有1个相似的兴趣，它将不等于[] / nil。

基本上我正在尝试的输出是一旦它们配对就将它们从参与者选择的阵列中移除，并且为了使它们配对，它们将必须与具有彼此最少兴趣的另一个参与者。

编辑：更新了代码，这是我尝试改进算法逻辑

for participant in 0..<participantsSelected {
    var maxInterestIndex = 10
    var currentIndex = 1
    for _ in 0..<participantsSelected {
        print (participant)
        print (currentIndex)
        let score = participantsAvailable[participant].interest.intersection(participantsAvailable[currentIndex].interest)
        print ("testing score, \(score.count)")
        if score.count < maxInterestIndex {
            maxInterestIndex = score.count
            print ("test, \(maxInterestIndex)")
        } else {
            pairsCreated.append(participantsAvailable[participant])
            pairsCreated.append(participantsAvailable[currentIndex])
            break
//            participantsAvailable.remove(at: participant)
//            participantsAvailable.remove(at: pairing)
        }
        currentIndex = currentIndex + 1
    }
}

for i in 0..<pairsCreated.count {
    print (pairsCreated[i].name)
}

Answer 1

这是一个解决方案，在这种情况下，您正在寻找的是根据您的标准最佳地配对您的参与者（所有人）： 然后，前进的方法是在参与者图表中找到完美的匹配。 使用n顶点创建图形，n是参与者的数量。我们可以用u_p表示对应于参与者p的顶点。 然后，创建加权边，如下所示： 对于每对参与者p, q（p！= q），创建边缘(u_p, u_q)，并用这两个参与者共同的兴趣数量来加权。 然后，在图表上运行最小权重完美匹配算法，完成工作。您将在多项式时间内获得最佳结果（意味着最佳结果，或最佳匹配之一）。

最小权重完美匹配算法：该问题严格等同于最大权重匹配算法。找到最大重量的边缘（让我们用C表示它的重量）。然后用w替换每条边的权重C-w，并在结果图上运行最大权重匹配算法。

我建议yoy使用Edmond's blossom algorithm在你的图表中找到一个完美的匹配。首先是因为它有效且记录良好，其次是因为我相信你可以在大多数现有语言中找到实现，但也因为它确实是一个非常非常漂亮的算法（它不被称为开花）。

另一种可能性，如果你确定你的参与者人数很少（你提到8），你也可以选择一个强力算法，这意味着要测试所有可能的方法来配对参与者。然后算法看起来像：

find_best_matching(participants, interests, pairs):
    if all participants have been paired:
        return sum(cost(p1, p2) for p1, p2 in pairs), pairs  // cost(p1, p2) = number of interests in common
    else:
        p = some participant which is not paired yet
        best_sum = + infinite
        best_pairs = empty_set
        for all participants q which have not been paired, q != p:
            add (p, q) to pairs
            current_sum, current_pairs = find_best_matching(participants, interests, pairs)
            if current_sum < best_sum:
                best_sum = current_sum
                best_pairs = current_pairs
            remove (p, q) from pairs
        return best_sum, best_pairs

最初使用find_best_matching(participants, interests, empty_set_of_pairs)调用它以获得匹配您的参与者的最佳方式。