possible pairings in a set

[Steven D'Aprano]

On Sat, 04 Apr 2009 17:42:58 -0700, Ross wrote:

> I'm new to python and I'm trying to come up with a function that takes a
> given number of players in a game and returns all possible unique
> pairings. Here's the code I've come up with so far, but I'm not getting
> the output I'd like to:

Others have already given a solution for Python 2.6, using 
itertools.combinations(). Here's a solution for Python 2.4 and 2.5.

The thing to remember about combinations is that they can be defined 
recursively. To find the combinations of [1, 2, 3, 4] we can do something 
like this: 

Combinations of [1, 2, 3, 4]:
  Start with the first item, 1.
  Combinations are given by [1] + combinations of what's left: [2, 3, 4].

  Combinations of [2, 3, 4]:
    Start with the first item, 2.
    Combinations are given by [2] + combinations of what's left: [3, 4].

    Combinations of [3, 4]:
      Start with the first item, 3.
      Combinations are given by [3] + combinations of what's left: [4].

      Combinations of [4]:
        Start with the first item, 4.
        Combinations are given by [4] + combinations of what's left: [].

        Combinations of []:
          There aren't any, so we're done.


Using that algorithm gives us this function:

def combinations(seq, r=None):
    """Generator returning combinations of items from sequence <seq>
    taken <r> at a time. Order is not significant. If <r> is not given,
    the entire sequence is returned.
    """
    if r == None:
        r = len(seq)
    if r <= 0:
        yield []
    else:
        for i in xrange(len(seq)):
            for cc in combinations(seq[i+1:], r-1):
                yield [seq[i]]+cc


def all_pairings(players):
    return list(combinations(range(players), 2))


> If I were to execute the function with all_pairings(4), I want to get
> the output [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3].


>>> all_pairings(4)
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]



-- 
Steven