Kiran Jonnalagadda’s Blog

I recently wrote some code that required iterating through all combinations of a list of lists. I couldn’t find an existing function to do this, so wrote one:

def listcombinations(listoflists, curlist=[], parents=[]):
    """
    Generator that yields all possible combinations from a list of lists.

    >>> a = [[1, 2], [3, 4], [5, 6], [7, 8]]
    >>> for c in listcombinations(a): print c
    ...
    [1, 3, 5, 7]
    [1, 3, 5, 8]
    [1, 3, 6, 7]
    [1, 3, 6, 8]
    [1, 4, 5, 7]
    [1, 4, 5, 8]
    [1, 4, 6, 7]
    [1, 4, 6, 8]
    [2, 3, 5, 7]
    [2, 3, 5, 8]
    [2, 3, 6, 7]
    [2, 3, 6, 8]
    [2, 4, 5, 7]
    [2, 4, 5, 8]
    [2, 4, 6, 7]
    [2, 4, 6, 8]
    """
    if curlist == []:
        curlist = listoflists[0]
        remlist = listoflists[1:]
    else:
        remlist = listoflists
    for item in curlist:
        if len(remlist) > 0:
            for c in listcombinations(remlist[1:], remlist[0], parents+[item]):
                yield c
        else:
            yield parents+[item]

In the code above, the function returns combinations in a sequence such that each consecutive combination differs by only one item. My use case required consecutive combinations to be as unlike each other as possible. After mulling over it a bit, I figured I’d just randomise the entire set. This presented a new problem. On a production run, it turned out my list of lists summed up to over three million combinations. I only needed about ten and, neither picking the first ten nor generating the full list and picking a random ten was feasible: insufficiently distinct or took too long, respectively.

The solution? A lazy list instead of a generator:

class Combinations:
    """
    Holds all possible combinations of a given list of lists. Behaves like
    a lazy list.

    >>> a = [[1, 2], [3, 4], [5, 6], [7, 8]]
    >>> for c in Combinations(a): print c
    ...
    [1, 3, 5, 7]
    [2, 3, 5, 7]
    [1, 4, 5, 7]
    [2, 4, 5, 7]
    [1, 3, 6, 7]
    [2, 3, 6, 7]
    [1, 4, 6, 7]
    [2, 4, 6, 7]
    [1, 3, 5, 8]
    [2, 3, 5, 8]
    [1, 4, 5, 8]
    [2, 4, 5, 8]
    [1, 3, 6, 8]
    [2, 3, 6, 8]
    [1, 4, 6, 8]
    [2, 4, 6, 8]
    >>> print Combinations(a)[12]
    [1, 3, 6, 8]
    """
    def _product(self, sequence):
        "Returns product of items in sequence."
        if not sequence: return 0
        return reduce(lambda x,y: x*y, sequence)

    def __init__(self, listoflists):
        self.length = self._product([len(col) for col in listoflists])
        self.listoflists = listoflists

    def __len__(self):
        return self.length

    def __getitem__(self, index):
        if index >= self.length:
            raise IndexError, "Index out of range."
        r = []
        p = 1
        for col in range(len(self.listoflists)):
            i = int(index/p) % len(self.listoflists[col])
            r.append(self.listoflists[col][i])
            p *= len(self.listoflists[col])
        return r

Here’s the code packaged as a Python module.