permuations of list of lists for ecommerce attributes

Q)  In a ecommerce product a product can have many attributes like size,color,gender. and again each attribute can have multiple values like size ['s,'m','L','XL','XXL'].
and color as ['red,'blue','brown'] and gender as ['M','F'].

A ecommerce product want to display all possible combinations of attributes. each attribute has multiple values and attribute list vary in length. ex: if color ['red,'blue','green','brown'] and gender as ['M','F']
then possible combos are [red,M],[red,F],[blue,M],[blue,F],[green,M], [green,F], [brown,M] , [brown,F]

Solution1: Just a recursive algo, which takes list as argument. for each element in list , get the permutations of remaining lists.

l = [['red', 'brown', 'black'], ['S','M','L', 'XL'], ['M','F']]

def permu(lists, prefix=''):

    if not lists:

        print prefix

        return

    first = lists[0]

    rest = lists[1:]

    for letter in first:

        permu(rest, prefix + letter +",")

permu(l)

Solution:2 make a m way tree. like root having children for 1st set of attributes. and for each node of attribute has next set of attributes as children.

            [root]
[red] [blue] [green] [brown]

[M] [F]

. Then doing a dfs till node and print the path to leaf will give different combinations of product.

In Python:

class Node(object):

    def __init__(self):

        self.data=''

        self.children=[]

                

class mway(object):

    def __init__(self):

        self.root=None

    def insert(self,list_string):

        if self.root is None:

            root=Node()

            root.data=''

            root.children=[]

            self.root=root            

        

        node=self.root

        list_nodes=[]    

        for i in list_string:

            node=Node()

            node.data=i

            node.children=[]

            list_nodes.append(node)

        #stack for insertion

        li_bt=[self.root]

        while len(li_bt) > 0:

            node=li_bt.pop()

            #print "popping %s"%(node.data)

            if len(node.children) == 0:

                for n in list_nodes:

                    node.children.append(n)

                    #print "appending %s to %s"%(n.data,node.data)

            else:

                for chi in node.children:

                    if chi not in list_nodes:

                        li_bt.append(chi)

                    

    def printcomb(self,node,string=""): #dfs to leaf and print path

        if len(node.children) == 0:

            print string

        for i in node.children:          

            self.printcomb(i,string+ i.data + ",")

            

    def getroot(self):

        return self.root

        

print "enter number of attributes"

li_all=[]

attr=int(raw_input())

while attr > 0:

    print "enter attributes seperated by ,"

    list_attr=str(raw_input()).split(",")

    li_all.append(list_attr)

    attr=attr-1

    

mtree=mway()

for iattr in li_all:

    mtree.insert(iattr)

    

node=mtree.getroot()

mtree.printcomb(node)