#!/usr/bin/env python2.3

"""
Code to generate all possible combinations of a list of lists
in two implementations, using a generator and a lazy list.
"""

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]


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


def _test():
    import doctest
    print "Running doctests..."
    doctest.testmod()

if __name__=='__main__':
    _test()