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.
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:
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)
