recursive function

C

cesco

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
 
N

Neil Cerutti

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))]

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()).
 
C

cesco

Neil said:
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))]

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
 
B

bearophileHUGS

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
 
M

Max Erickson

cesco said:
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

This thread is probably of interest:

http://groups.google.com/group/comp.lang.python/browse_frm/thread/f0c0
406fce981a54/59a2a5dcd1507ab9#59a2a5dcd1507ab9


max
 
H

Hendrik van Rooyen

cesco said:
Neil said:
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))]

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
 
C

cesco

Hendrik said:
cesco said:
Neil said:
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))]

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 (e-mail address removed) was
quite satisfactory:)

regards
Cesco
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top