Velocity Reviews > recursive function

# recursive function

cesco
Guest
Posts: n/a

 01-08-2007
Hi,

I have a dictionary of lists of tuples like in the following example:
dict = {1: [(3, 4), (5, ],
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, , (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?

Francesco

Neil Cerutti
Guest
Posts: n/a

 01-08-2007
On 2007-01-08, cesco <(E-Mail Removed)> wrote:
> Hi,
>
> I have a dictionary of lists of tuples like in the following example:
> dict = {1: [(3, 4), (5, ],
> 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, , (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

cesco
Guest
Posts: n/a

 01-08-2007

Neil Cerutti wrote:
> On 2007-01-08, cesco <(E-Mail Removed)> wrote:
> > Hi,
> >
> > I have a dictionary of lists of tuples like in the following example:
> > dict = {1: [(3, 4), (5, ],
> > 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, , (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

bearophileHUGS@lycos.com
Guest
Posts: n/a

 01-08-2007
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, ],
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

Tim Williams
Guest
Posts: n/a

 01-08-2007
On 8 Jan 2007 16:03:53 +0100, Neil Cerutti <(E-Mail Removed)> wrote:

>
> len(dict.keys()).
>

Or

len(dict)

Max Erickson
Guest
Posts: n/a

 01-08-2007
"cesco" <(E-Mail Removed)> wrote:

> Hi,
>
> I have a dictionary of lists of tuples like in the following
> example: dict = {1: [(3, 4), (5, ],
> 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, ,
> (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?
>
> Francesco
>

This thread is probably of interest:

406fce981a54/59a2a5dcd1507ab9#59a2a5dcd1507ab9

max

Hendrik van Rooyen
Guest
Posts: n/a

 01-09-2007

"cesco" <(E-Mail Removed)> wrote:

>
> Neil Cerutti wrote:
> > On 2007-01-08, cesco <(E-Mail Removed)> wrote:
> > > Hi,
> > >
> > > I have a dictionary of lists of tuples like in the following example:
> > > dict = {1: [(3, 4), (5, ],
> > > 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, , (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

cesco
Guest
Posts: n/a

 01-09-2007

Hendrik van Rooyen wrote:
> "cesco" <(E-Mail Removed)> wrote:
>
> >
> > Neil Cerutti wrote:
> > > On 2007-01-08, cesco <(E-Mail Removed)> wrote:
> > > > Hi,
> > > >
> > > > I have a dictionary of lists of tuples like in the following example:
> > > > dict = {1: [(3, 4), (5, ],
> > > > 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, , (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 Removed) was
quite satisfactory

regards
Cesco