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.