从列表中形成随机配对（有点像……）

Question

跳到最后的编辑

我有一份包含多个 Person 对象的列表，我需要用一个叫 randomize_pairs 的函数随机将他们配对。每个 Person 对象都有一个属性 target，表示他们配对的对象。

我的限制条件是：没有人可以和自己配对（这很明显），而且不能和同一个人配对两次。

我通过创建一个临时列表，并在满足条件时将人从中移除来实现这个功能，但我相信还有更简洁、更好的、更符合 Python 风格的方法。有人知道吗？

---

编辑

在这个问题中，我用了很多“配对”这个词，但其实用词不太准确。这是一个游戏，每个人会被分配给另一个人作为目标，所以这些关系是单向的，你的目标不一定是你的目标。

目标只会在每轮开始时更改，所以是一次性完成的。

---

编辑 2

这是我目前决定的方法 虽然还有改进的空间，所以我会把问题保持开放。

def randomize_targets(players):
    # get player count
    count = len(players)
    # copy the list of players
    available_targets = list(players)
    # shuffle the player order so if the last one has to have the same
    # target twice it's not always the same player
    players = list(players)
    random.shuffle(players)
    # loop over each player
    for player in players:
        # get the list of possible targets
        potential_targets = [target for target in available_targets \
                             if target != player \
                             and target != player.target]
        # try to pick one at random
        try:
            target = random.choice(potential_targets)
        # if we have to, use the same target as last time
        except IndexError:
            pass
        # remove the target from the available targets list
        available_targets.remove(target)
        # assign target
        player.target = target

---

编辑 3

我选择了这个方法，尽管我不喜欢可能需要很长时间循环才能找到有效组合的情况，但至少它总是能得到有效的结果。

def randomize_targets2 (players):
    targets = list(players)
    # run this until it generates a valid result
    valid = False
    while not valid:
        # randomize the targets
        random.shuffle(targets)
        # validate them
        round_valid = True
        for player, target in zip(players, targets):
            round_valid = round_valid and player != target and player.target != target
        valid = round_valid

    # apply the validated targets
    for player, target in zip(players, targets):
        player.target = target

Answer 1

我来这里是为了找解决同样问题的方法，但在你自己在编辑3中给出的答案上遇到了一些问题。于是我得出了一个结果，这个结果似乎避免了不必要的长循环：

"""Random Pairings Generator"""
import random
import json
def random_matches(players):
    """
    Generates a dict of random pairings from two lists
    preserves original lists
    """
    matching_dict = {}
    players_tmp = players[:]
    targets_tmp = players[:]
    random.shuffle(targets_tmp)
    for player in players_tmp:
        random.shuffle(targets_tmp)
        target = targets_tmp.pop(random.randrange(len(targets_tmp)))
        while target == player:
            targets_tmp.append(target)
            random.shuffle(targets_tmp)
            target = targets_tmp.pop(random.randrange(len(targets_tmp)))
        matching_dict[player] = target
    print json.dumps(matching_dict, indent=2, separators=(',', ': '), sort_keys=True)
    return matching_dict

这里提升性能的关键在于减少了targets_tmp中的可选项。示例输出：

>>> players = ['dad', 'mom', 'brother', 'sister', 'uncle', 'aunt', 'wife', 'grandma', 'grandpa', 'brother-in-law', 'nephew']
>>> random_matches(players)
{
  "aunt": "brother",
  "brother": "grandma",
  "brother-in-law": "aunt",
  "dad": "grandpa",
  "grandma": "sister",
  "grandpa": "nephew",
  "mom": "dad",
  "nephew": "uncle",
  "sister": "wife",
  "uncle": "mom",
  "wife": "brother-in-law"
}

因为我们主动从targets_tmp中移除了已经匹配的目标，所以在遍历players_tmp时，每个玩家的可能匹配项大大减少，这样就减少了每次循环中while target == player所花费的时间。

Answer 2

你可以用你的列表来获取所有可用的人的集合。
接着，你可以创建一个字典，把每个人和他们已经配对过的人的集合对应起来（每个人的集合里也要包含自己）。
然后，对于每个人，你可以从所有人中减去他们已经配对过的人的集合，这样就能得到一个可以随机选择的集合（使用random.sample来随机选择）。这种集合减法的方式效率应该挺高的。
你还需要确保，如果你把A和B配对了，当轮到B的时候，你能注意到这个配对，然后就跳过这次配对。
当然，别忘了更新你的字典，把新的配对记录下来，这样就不会再配对到同样的人了。
我觉得这个方法很优雅，因为你可以很容易地添加一些忽略规则（比如A永远不想和B配对），只需要把这些规则加到相关的集合里就行了。

Answer 3

我想你是想随机选择一些人，所以你选择的列表应该能快速访问。一个简单的办法就是把整个列表打乱，然后从列表的前面两两配对。

Fisher-Yates 洗牌算法是一种快速且简单的随机打乱列表的方法。

然后你可以直接遍历这个列表，把人配对起来：

for x from 0 to persons.size(), x += 2
    pair(persons.get(i), persons.get(i + 1));

因为每个人都是独一无二的，所以你不用担心会有人被配对两次或者和自己配对。

另外要注意，确保你的列表里有偶数个人！如果总人数是奇数，你就得想办法处理最后多出来的那个人。