Find most efficient groups of pairs

This is an implementation of the algorithm described in the Wikipedia article Round-robin tournament.

from itertools import cycle , islice, chaindef round_robin(iterable):    items = list(iterable)    if len(items) % 2 != 0:        items.append(None)    fixed = items[:1]    cyclers = cycle(items[1:])    rounds = len(items) - 1    npairs = len(items) // 2    return [        list(zip(            chain(fixed, islice(cyclers, npairs-1)),            reversed(list(islice(cyclers, npairs)))        ))        for _ in range(rounds)        for _ in [next(cyclers)]    ]

I generate just the indices (because I have trouble coming up with 1000 names =), but for 1000 numbers the runtime is about 4 seconds.

The main problem of all other approaches -- they use pairs and work with them, there are plenty of pairs, and the run time is getting much longer. My approach differs in working with people, not pairs. I have a dict() that maps the person to the list of other persons (s)he has to meet, and these lists are at most N items long (not N^2, as with pairs). Hence the time savings.

#!/usr/bin/env pythonfrom itertools import combinationsfrom collections import defaultdictpairs = combinations( range(6), 2 )pdict = defaultdict(list)for p in pairs :    pdict[p[0]].append( p[1] )while len(pdict) :    busy = set()    print '-----'    for p0 in pdict :        if p0 in busy : continue        for p1 in pdict[p0] :            if p1 in busy : continue            pdict[p0].remove( p1 )            busy.add(p0)            busy.add(p1)            print (p0, p1)            break    # remove empty entries    pdict = { k : v for k,v in pdict.items() if len(v) > 0 }'''output:-----(0, 1)(2, 3)(4, 5)-----(0, 2)(1, 3)-----(0, 3)(1, 2)-----(0, 4)(1, 5)-----(0, 5)(1, 4)-----(2, 4)(3, 5)-----(2, 5)(3, 4)'''

When you need fast lookups hashes/dicts are the way to go. Keep track of whose been in each round in a dict rather than a list and it will be much faster.

Since you are getting in algorithms, studying big O notation will help you out and knowing what data structures are good at what kind of operations is also key. See this guide: https://wiki.python.org/moin/TimeComplexity for time complexity of Python built-ins. You'll see that checking for an item in a list is O(n) meaning that it scales linearly with the size of your inputs. So since it is in a loop you end up with O(n^2) or worse. For dicts, lookups are generally O(1) meaning that it doesn't matter the size of your input.

Also, don't override built-ins. I'd changed round to round_

from itertools import combinations# test if person already exists in any pairing inside a round of pairsdef person_in_round(person, people_dict):    return people_dict.get(person, False)def make_rounds(people):    people_pairs = set(combinations(people, 2))    people_in_round = {}    # we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty    while people_pairs:        round_ = []        people_dict = {}        # make a copy of the current state of people_pairs to iterate over safely        for pair in set(people_pairs):            if not person_in_round(pair[0], people_dict) and not person_in_round(pair[1], people_dict):                round_.append(pair)                people_dict[pair[0]] = True                people_dict[pair[1]] = True                people_pairs.remove(pair)        yield round_