CODEWITHSUNDEEP
pythoncombinationspermutationpseudocode
Akshay Hazari
Akshay Hazari

Reputation: 3267

Permutations of list of lists

Supposing there is a list of list of elements. Where each list can have any no of elements. For example [[1,2,3,4],[2,3],[4,5,6,7],[1]] . I am trying to generate permutations of such lists possible where I am supposed to select only one from the innermost lists in one such permutation. So the output will be [1,2,4,1],[1,3,4,1]...

Sample Input = [[1,2],[3],[4]]
Sample output = [[1,3,4],[2,3,4]]

I had tried some code earlier which had a flawed logic. Following is the code in which I am mid way and stuck. I am no able to get an approach to it. I am not good at Permutations and Combinations.

what I am trying is the same as described above just that the following are set of coordinates. i,e the innermost elements(in input) are set of coordinates.

[[[1,2],[2,4]],[[2,3],[4,2]],[[1,5]],[[3,3],[7,2],[5,6]]]

def perm(a,length):
    arr=[]
    k=0
    while (k<length):
        temp=[]
        for i in a:


a=[[[1,2],[2,4]],[[2,3],[4,2]],[[1,5]],[[3,3],[7,2],[5,6]]]
perm(a)

Please let me know for further clarifications. Any help is appreciated.

Edit

I would want a solution without using itertools or any such python module. I should have mentioned it before. otherwise it is a valid and very handy solution.

Psuedo code Logic for answer will do or a simple answer with an approach instead of using python library. Sorry about adding this detail late.

Upvotes: 1

Views: 1597

Answers (2)

usual me
usual me

Reputation: 8798

I find the following recursive version more readable than the one using list comprehension, but I guess that's a matter of taste:

def cartesianProduct( *lists ) :
    if not lists : # nothing to do, yield empty tuple
        yield ()
    else : # let's do A x cartesianProduct( B x C x ... )
        for a in lists[0] : # each element of A
            for tup in cartesianProduct( *lists[1:] ) : # each tuple of ( B x C x ... )
                yield ( a, ) + tup # concatenate and yield 

list( product( 'AB', range(3), 'xy' ) ) == list( cartesianProduct('AB', range(3), 'xy') )

True

Upvotes: 2

jonrsharpe
jonrsharpe

Reputation: 122150

You can do this easily with itertools.product:

>>> from itertools import product
>>> list(product(*[[1,2],[3],[4]]))
[(1, 3, 4), (2, 3, 4)]
>>> list(product(*[[1,2,3,4],[2,3],[4,5,6,7],[1]]))
[(1, 2, 4, 1), (1, 2, 5, 1), (1, 2, 6, 1), (1, 2, 7, 1), 
 (1, 3, 4, 1), (1, 3, 5, 1), (1, 3, 6, 1), (1, 3, 7, 1), 
 (2, 2, 4, 1), (2, 2, 5, 1), (2, 2, 6, 1), (2, 2, 7, 1), 
 (2, 3, 4, 1), (2, 3, 5, 1), (2, 3, 6, 1), (2, 3, 7, 1), 
 (3, 2, 4, 1), (3, 2, 5, 1), (3, 2, 6, 1), (3, 2, 7, 1), 
 (3, 3, 4, 1), (3, 3, 5, 1), (3, 3, 6, 1), (3, 3, 7, 1), 
 (4, 2, 4, 1), (4, 2, 5, 1), (4, 2, 6, 1), (4, 2, 7, 1), 
 (4, 3, 4, 1), (4, 3, 5, 1), (4, 3, 6, 1), (4, 3, 7, 1)]

A nearly-equivalent implementation without any imports, per the documentation:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Upvotes: 2

Related Questions