Word combinations (cartesian product)

combinations.py

def combinations(ll, j=0, cll=None):
    '''Returns a list of word combinations.
    
    Generates recursively a cartesian product for given possibilities.
    
    Note: This function consumes a lot of memory for large words with many possibilities.
    
    Example:
    
        >>> ll = [[u'h'], [u'e', u'a'], [u'l', u'll'], [u'o']]
        >>> combinations(ll)
        [u'hallo', u'halo', u'hello', u'helo']
        
    '''

    if cll is None:
        cll = list(ll)

    if all(isinstance(l, unicode) for l in ll):
        return [''.join(ll)]
    else:
        res = []

        for i, l in enumerate(ll):
            if i > j:
                ll[i] = cll[i]

            if isinstance(l, list):
                x, xs = l[0], l[1:] if len(l) > 1 else None

                if xs is not None:
                    ll[i] = xs
                    res += combinations(ll, i, cll)

                ll[i] = x

        res += combinations(ll, i-1, cll)

        return res

if you look for something which consumes less memory use the python built-in product function from itertools.

Here is a nice solution: http://stackoverflow.com/a/25380524, but seems to be slower...