443,818 Members | 1,282 Online
Need help? Post your question and get tips & solutions from a community of 443,818 IT Pros & Developers. It's quick & easy.

# recursive function

 P: n/a Hi, I have a dictionary of lists of tuples like in the following example: dict = {1: [(3, 4), (5, 8)], 2: [(5, 4), (21, 3), (19, 2)], 3: [(16, 1), (0, 2), (1, 2), (3, 4)]] In this case I have three lists inside the dict but this number is known only at runtime. I have to write a function that considers all the possible combinations of tuples belonging to the different lists and return a list of tuples of tuples for which the sum of the first element of the most inner tuple is equal to N. For example, assuming N = 24, in this case it should return: [((3, 4), (5, 4), (16, 1)), ((3, 4), (21, 3), (0, 2)), ((5, 8), (19, 2), (0, 2))] A simple list comprehension would be enough if only I knew the number of keys/lists beforehand but this is not the case. I guess I need a recursive function. Can anyone help? Thanks in advance Francesco Jan 8 '07 #1
7 Replies

 P: n/a On 2007-01-08, cesco

 P: n/a Neil Cerutti wrote: On 2007-01-08, cesco

 P: n/a First possible solution: def rloop(seqin, comb): # xcross product recipe 302478 by David Klaffenbach if seqin: for item in seqin[0]: newcomb = comb + [item] for item in rloop(seqin[1:], newcomb): yield item else: yield comb data = {1: [(3, 4), (5, 8)], 2: [(5, 4), (21, 3), (19, 2)], 3: [(16, 1), (0, 2), (1, 2), (3, 4)]} print [sol for sol in rloop(data.values(), []) if 24==sum(el[0] for el in sol)] Bye, bearophile Jan 8 '07 #4

 P: n/a On 8 Jan 2007 16:03:53 +0100, Neil Cerutti len(dict.keys()). Or len(dict) :) Jan 8 '07 #5

 P: n/a "cesco"

 P: n/a "cesco" Neil Cerutti wrote: On 2007-01-08, cesco I have a dictionary of lists of tuples like in the following example: dict = {1: [(3, 4), (5, 8)], 2: [(5, 4), (21, 3), (19, 2)], 3: [(16, 1), (0, 2), (1, 2), (3, 4)]] > In this case I have three lists inside the dict but this number is known only at runtime. I have to write a function that considers all the possible combinations of tuples belonging to the different lists and return a list of tuples of tuples for which the sum of the first element of the most inner tuple is equal to N. > For example, assuming N = 24, in this case it should return: [((3, 4), (5, 4), (16, 1)), ((3, 4), (21, 3), (0, 2)), ((5, 8), (19, 2), (0, 2))] What do you mean by "most inner tuple"? A simple list comprehension would be enough if only I knew the number of keys/lists beforehand len(dict.keys()). What I mean is that the number of keys/lists is not known until runtime and it changes randomly from time to time which means I would have to write every time a different list comprehension (or a different number of nested loops) to accomplish the same thing. In the example the result of the search should be a list containing three tuples each of which contains again three tuple (the most inner tuples). If you consider the first element of each tuple the sum is 24 (like in 3+5+16, or 3+21+0 or 5+19+0). Any other help will be appreciated Is there any reliable structure in the data? - for instance in your example, the first list has two tuples, the second one three, and the third one four - Is this a pattern? - Hendrik Jan 9 '07 #7

 P: n/a Hendrik van Rooyen wrote: "cesco" What do you mean by "most inner tuple"? > A simple list comprehension would be enough if only I knew the number of keys/lists beforehand > len(dict.keys()). What I mean is that the number of keys/lists is not known until runtime and it changes randomly from time to time which means I would have to write every time a different list comprehension (or a different number of nested loops) to accomplish the same thing. In the example the result of the search should be a list containing three tuples each of which contains again three tuple (the most inner tuples). If you consider the first element of each tuple the sum is 24 (like in 3+5+16, or 3+21+0 or 5+19+0). Any other help will be appreciated Is there any reliable structure in the data? - for instance in your example, the first list has two tuples, the second one three, and the third one four - Is this a pattern? Hi Hendrik, there is no such a pattern (I just happened to insert that ascending number of lists). Anyway the answer from bearophileH...@lycos.com was quite satisfactory:-) regards Cesco Jan 9 '07 #8

### This discussion thread is closed

Replies have been disabled for this discussion.