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)

No comments: