recursive function

Discussion in 'Python' started by cesco, Jan 8, 2007.

  1. cesco

    cesco Guest

    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
    cesco, Jan 8, 2007
    #1
    1. Advertising

  2. cesco

    Neil Cerutti Guest

    On 2007-01-08, cesco <> wrote:
    > 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
    Neil Cerutti, Jan 8, 2007
    #2
    1. Advertising

  3. cesco

    cesco Guest

    Neil Cerutti wrote:
    > On 2007-01-08, cesco <> wrote:
    > > 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
    cesco, Jan 8, 2007
    #3
  4. cesco

    Guest

    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, 2007
    #4
  5. cesco

    Tim Williams Guest

    On 8 Jan 2007 16:03:53 +0100, Neil Cerutti <> wrote:

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


    Or

    len(dict)

    :)
    Tim Williams, Jan 8, 2007
    #5
  6. cesco

    Max Erickson Guest

    "cesco" <> wrote:

    > 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
    Max Erickson, Jan 8, 2007
    #6
  7. "cesco" <> wrote:

    >
    > Neil Cerutti wrote:
    > > On 2007-01-08, cesco <> wrote:
    > > > 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
    Hendrik van Rooyen, Jan 9, 2007
    #7
  8. cesco

    cesco Guest

    Hendrik van Rooyen wrote:
    > "cesco" <> wrote:
    >
    > >
    > > Neil Cerutti wrote:
    > > > On 2007-01-08, cesco <> wrote:
    > > > > 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 was
    quite satisfactory:)

    regards
    Cesco
    cesco, Jan 9, 2007
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tyron

    Recursive function

    Tyron, Apr 16, 2004, in forum: VHDL
    Replies:
    1
    Views:
    627
    valentin tihomirov
    Apr 16, 2004
  2. n00m
    Replies:
    12
    Views:
    1,112
  3. vamsi
    Replies:
    21
    Views:
    2,072
    Keith Thompson
    Mar 9, 2009
  4. Mark Piffer
    Replies:
    9
    Views:
    907
    luserXtrog
    May 15, 2009
  5. Alok
    Replies:
    3
    Views:
    249
Loading...

Share This Page