Generating all possible combinations from a list of lists
Question: I have the following lists:

    
    
    [[a,b,c],[b],[d,a,b,e],[a,c]]
    

This list represents a mini-world in a puzzle problem. In this example the
world contains 4 piles of objects stacked on-top of each other. I can only
move the top object and place it on-top of some other stack. The letters
represent a type of object, for example a might be a rock and b a ball. I need
to generate all possible states that can exist for this mini-world. Im trying
to do this in python but don't know how to implement it.


Answer: You can use
[itertools.combinations_with_replacement](http://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement)
with list comprehension:

    
    
    import itertools
    ll = [['a','b','c'],['b'],['d','a','b','e'],['a','c']]
    print [list(itertools.combinations_with_replacement(item,len(item))) for item in ll] 
    

It gives the combinations for each element in list of lists.

Output:

    
    
     [[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'b'), ('a', 'b', 'c'), ('a', 'c', 'c'), ('b', 'b', 'b'), ('b', 'b', 'c'), ('b', 'c', 'c'), ('c', 'c', 'c')], 
     [('b',)], 
     [('d', 'd', 'd', 'd'), ('d', 'd', 'd', 'a'), ('d', 'd', 'd', 'b'), ('d', 'd', 'd', 'e'), ('d', 'd', 'a', 'a'), ('d', 'd', 'a', 'b'), ('d', 'd', 'a', 'e'), ('d', 'd', 'b', 'b'), ('d', 'd', 'b', 'e'), ('d', 'd', 'e', 'e'), ('d', 'a', 'a', 'a'), ('d', 'a', 'a', 'b'), ('d', 'a', 'a', 'e'), ('d', 'a', 'b', 'b'), ('d', 'a', 'b', 'e'), ('d', 'a', 'e', 'e'), ('d', 'b', 'b', 'b'), ('d', 'b', 'b', 'e'), ('d', 'b', 'e', 'e'), ('d', 'e', 'e', 'e'), ('a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'e'), ('a', 'a', 'b', 'b'), ('a', 'a', 'b', 'e'), ('a', 'a', 'e', 'e'), ('a', 'b', 'b', 'b'), ('a', 'b', 'b', 'e'), ('a', 'b', 'e', 'e'), ('a', 'e', 'e', 'e'), ('b', 'b', 'b', 'b'), ('b', 'b', 'b', 'e'), ('b', 'b', 'e', 'e'), ('b', 'e', 'e', 'e'), ('e', 'e', 'e', 'e')], 
     [('a', 'a'), ('a', 'c'), ('c', 'c')]]
    

If you would like to avoid duplicate same element in a combination, you can
use
[itertools.permutation](http://docs.python.org/2/library/itertools.html#itertools.permutations):

    
    
     [list(itertools.permutations(item,len(item))) for item in ll] 
    

Output:

    
    
    [[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')], 
    [('b',)], 
    [('d', 'a', 'b', 'e'), ('d', 'a', 'e', 'b'), ('d', 'b', 'a', 'e'), ('d', 'b', 'e', 'a'), ('d', 'e', 'a', 'b'), ('d', 'e', 'b', 'a'), ('a', 'd', 'b', 'e'), ('a', 'd', 'e', 'b'), ('a', 'b', 'd', 'e'), ('a', 'b', 'e', 'd'), ('a', 'e', 'd', 'b'), ('a', 'e', 'b', 'd'), ('b', 'd', 'a', 'e'), ('b', 'd', 'e', 'a'), ('b', 'a', 'd', 'e'), ('b', 'a', 'e', 'd'), ('b', 'e', 'd', 'a'), ('b', 'e', 'a', 'd'), ('e', 'd', 'a', 'b'), ('e', 'd', 'b', 'a'), ('e', 'a', 'd', 'b'), ('e', 'a', 'b', 'd'), ('e', 'b', 'd', 'a'), ('e', 'b', 'a', 'd')], 
    [('a', 'c'), ('c', 'a')]]
    

