By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,818 Members | 1,282 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
7 Replies


P: n/a
On 2007-01-08, cesco <fd**********@gmail.comwrote:
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()).

--
Neil Cerutti
Next Sunday Mrs. Vinson will be soloist for the morning service. The pastor
will then speak on "It's a Terrible Experience." --Church Bulletin Blooper
Jan 8 '07 #2

P: n/a

Neil Cerutti wrote:
On 2007-01-08, cesco <fd**********@gmail.comwrote:
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

Jan 8 '07 #3

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 <ho*****@yahoo.comwrote:
>
len(dict.keys()).
Or

len(dict)

:)
Jan 8 '07 #5

P: n/a
"cesco" <fd**********@gmail.comwrote:
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....rm/thread/f0c0
406fce981a54/59a2a5dcd1507ab9#59a2a5dcd1507ab9
max

Jan 8 '07 #6

P: n/a

"cesco" <fd**********@gmail.comwrote:
>
Neil Cerutti wrote:
On 2007-01-08, cesco <fd**********@gmail.comwrote:
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
Jan 9 '07 #7

P: n/a

Hendrik van Rooyen wrote:
"cesco" <fd**********@gmail.comwrote:

Neil Cerutti wrote:
On 2007-01-08, cesco <fd**********@gmail.comwrote:
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 bearophileH...@lycos.com was
quite satisfactory:-)

regards
Cesco

Jan 9 '07 #8

This discussion thread is closed

Replies have been disabled for this discussion.