Generating multiple lists from one list

Discussion in 'Python' started by Girish Sahani, Jul 5, 2006.

  1. hello ppl,

    Consider a list like ['a.1','b.3','b.4','c.2']. Here 'a','b','c' are
    objects and 1,3,4,2 are their instance ids and they are unique e.g. a.1
    and b.1 cannot exist together. From this list i want to generate
    multiple lists such that each list must have one and only one instance
    of every object.
    Thus, for the above list, my output should be:
    [['a.1','b.3','c.2'],['a.1','b.4','c.2']]
    Another example: Let l = ['a.1','b.3','b.4','c.2','c.6','d.3']. Then
    output should be [['a.1','b.3','c.2','d.3'],['a.1','b.3','c.6','d.3'],
    ['a.1','b.4','c.2','d.3'],[['a.1','b.4','c.6','d.3']

    Can anyone suggest me a time-efficient method for doing this??

    TIA,
    girish
     
    Girish Sahani, Jul 5, 2006
    #1
    1. Advertising

  2. # first step : build a dictionary mapping the objects
    # to all possible ids

    alist = ['a.1','b.3','b.4','c.2','c.6','d.3']
    elts = {}
    for item in alist:
    obj=item.split('.')[0]
    if elts.has_key(obj):
    elts[obj].append(item)
    else:
    elts[obj] = [item]

    # then build the Python code that will iterate
    # on all the possible values

    ks = elts.keys()
    ks.sort()

    p_code = ''
    for i,k in enumerate(ks):
    p_code += i*' ' + "for item%s in elts['%s']:\n" %(i,k)
    p_code += len(ks)*' '+'print ['+','.join([ "item%s" %i
    for i,k in enumerate(ks) ])+']'

    # print the code
    print p_code

    >for item0 in elts['a']:
    > for item1 in elts['b']:
    > for item2 in elts['c']:
    > for item3 in elts['d']:
    > print [item0,item1,item2,item3]


    # execute this code
    exec p_code

    >['a.1', 'b.3', 'c.2', 'd.3']
    >['a.1', 'b.3', 'c.6', 'd.3']
    >['a.1', 'b.4', 'c.2', 'd.3']
    >['a.1', 'b.4', 'c.6', 'd.3']


    It works, but there are probably more elegant ways to do it

    Just a question : in your message you say that 'a.1' and 'b.1' can not
    exist together, but in the example there are lists with both 'b.3' and
    'd.3' : should such lists be filtered ?

    Regards,
    Pierre
     
    Pierre Quentel, Jul 5, 2006
    #2
    1. Advertising

  3. Girish Sahani

    Anand Guest

    > p_code = ''
    > for i,k in enumerate(ks):
    > p_code += i*' ' + "for item%s in elts['%s']:\n" %(i,k)
    > p_code += len(ks)*' '+'print ['+','.join([ "item%s" %i
    > for i,k in enumerate(ks) ])+']'
    >
    > # print the code
    > print p_code
    >
    > >for item0 in elts['a']:
    > > for item1 in elts['b']:
    > > for item2 in elts['c']:
    > > for item3 in elts['d']:
    > > print [item0,item1,item2,item3]

    >
    > # execute this code
    > exec p_code


    This is not very nice. you can use recursion instead of generating
    code.

    The following solution first divides the given list into groups based
    on the first token and computes their cross product using recursion.

    def get_groups(x):
    """Groups the elements of the list x using the first token of the
    elment.
    All elements are expected of the form "a.n".
    for example:
    >>> get_groups(["a.1", "b.2", "a.2"])

    [["a.1", "a.2"], ["b.1"]]
    """
    groups = {}

    for item in x:
    a, n = item.split('.')

    if a not in groups:
    groups[a] = []

    groups[a].append(item)

    keys = groups.keys()
    keys.sort()

    return [groups[k] for k in keys]

    def cross_product(items):
    """
    computes cross product of the list of lists.
    example:
    >>> cross_product([["a", "b"], ["c"]])

    [["a", "b"], ["a", "c"]]
    """
    if not items:
    return [[]]

    x = items[-1]
    result = cross_product(items[:-1])

    return [a + for a in result for b in x]


    x = ['a.1','b.3','b.4','c.2','c.6','d.3']

    print cross_product(get_groups(x))
     
    Anand, Jul 6, 2006
    #3
    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. Chris Ritchey
    Replies:
    7
    Views:
    483
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    472
    emerth
    Jul 10, 2003
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    409
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. Girish Sahani

    Generating multiple lists from one list

    Girish Sahani, Jul 6, 2006, in forum: Python
    Replies:
    1
    Views:
    289
    Gerard Flanagan
    Jul 6, 2006
  5. cesco

    generating list of sub lists

    cesco, Sep 16, 2007, in forum: Python
    Replies:
    5
    Views:
    283
    Steven D'Aprano
    Sep 17, 2007
Loading...

Share This Page