Generating multiple lists from one list

[Girish Sahani]

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

 

[Pierre Quentel]

# 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

 

[Anand]

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