forming random pairs from a list (sort of…)

问题:

Skip to the last edit

I have a list of Person objects and I need to pair them off randomly with a randomize_pairs function, each Person object has a property target of who they are paired with.

My constraints are that no-one can pair with themselves (duh) and they shouldn't be paired with the same person twice.

I got this working by making a temporary list and popping people off if the constraints were satisfied but I'm sure there is a cleaner/better/more pythonic way of doing this. Anyone know?

---

edit

I used the word "pair" a lot in this question but that was the wrong word. This is for a game where each person is assigned another person as a target so these are one way relationships where your target's target is not necessarily you.

Targets will only be changed at the beginning of each round so it's all at once.

---

edit 2

Here's what I've settled on for now though it can be improved so I'm leaving the question open.

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

---

edit 3

I decided on this method even though I don't like the potentially long time looping until it finds a combo that works at least it always yields valid results

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

回答1:

I assume that since you want to select people at random, your choice of list provides fast random access. A simple solution is just to shuffle the whole list, and just pair people off in pairs from the front of the list.

The Fisher-Yates shuffle is a quick, easy way to shuffle the list randomly.

Then you can just run through and pair them off:

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

Since the elements are unique, you won't have to worry about people getting paired twice or with themselves.

Also be careful to make sure your list has an even number of people first! If the total is odd you'll have to deal with the extra person at the end of the list somehow.

回答2:

You can use your list to get a set of all people available.
You also make a dict mapping every person to a set of all people they have already been paired with (and also include each person in their own set).
Then for every person, you can subtract the set of all people with the set of people they have already been paired with and sample any item of that set (using random.sample) (set subtraction is probably pretty efficient).
You would also need to make sure that if you paired person A with person B, then when person B's turn comes, you notice the existing pairing and just skip that iteration.
And of course, don't forget to then update your dict with the new pairings, so that you don't ever end up making the same pairings again.
This method seems elegant to me because it will be easy for you to add arbitrary ignore rules (i.e. person A never wants to be paired with person B) by simply adding them in the relevant sets.

回答3:

I came here searching for a solution to the same problem, but I ran into a few issues with the answer you provide yourself in edit 3. This is the result I came to, which seems to avoid the unnecessarily long while loop:

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

They key to the performance improvement here was the reduction of available choices in targets_tmp. Sample output:

>>> 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"
}

Because we are proactively removing matched targets from targets_tmp, we greatly reduce the possible matches for each player as we iterate through players_tmp, thereby reducing the potential time spent within while target == player during each iteration.