Combinations of lists

[Steen Lysgaard]

Hi,

I am looking for a clever way to compute all combinations of two lists.
Look at this example:

h = ['A','A','B','B']
m = ['a','b']

the resulting combinations should be of the same length as h and each
element in m can be used twice. The sought after result using h and m
from above is:

[['aA', 'aA', 'bB', 'bB'],
['aA', 'aB', 'bA', 'bB'],
['aB', 'aB', 'bA', 'bA']]

(the order of the results does not matter i.e. ['aA', 'aA', 'bB', 'bB']
and ['aA', 'bB', 'aA', 'bB'] are considered the same)

This is achieved by the code below, this however needs to go through all
possible combinations (faculty of len(h)) and rule out duplicates as
they occur and this is too much if for example len(h) is 16.

Can anyone guide me to a better solution?

Thanks,
Steen

h = ['A','A','B','B']
m = ['a','b']

c = []
for i in h:
c.append([])
for j in m:
c[-1].append(j+i)
c[-1].append(j+i)

combs = []

for a in permutations(range(len(h)),len(h)):
comb = []
for i in range(len(h)):
comb.append(c[a])
comb.sort()

if comb not in combs:
combs.append(comb)

print combs

print len(combs)

 

[Alain Ketterlin]

I am looking for a clever way to compute all combinations of two
lists. Look at this example:

h = ['A','A','B','B']
m = ['a','b']

the resulting combinations should be of the same length as h and each
element in m can be used twice. The sought after result using h and m
from above is:

[['aA', 'aA', 'bB', 'bB'],
['aA', 'aB', 'bA', 'bB'],
['aB', 'aB', 'bA', 'bA']]

I can't make sense of your explanation, which doesn't seem to match your
example (the result is not of the same size as h).

Here is a way to compute { xh | x in m }, where xh is a list where x is
prepended to each element of h.

result = [ [ x+l for l in h ] for x in m ]

If there is no duplicate in the original lists, then there will be no
duplicate in the result. Is that what you are looking for?

-- Alain.

 

[Steven D'Aprano]

Hi,

I am looking for a clever way to compute all combinations of two lists.
Look at this example:

h = ['A','A','B','B']
m = ['a','b']

the resulting combinations should be of the same length as h and each
element in m can be used twice.

Why twice? What if you had these?

h = ['A', 'A', 'B', 'B', 'C', 'D', 'E', 'E']
m = ['a', 'b', 'c']

Would you still use each element in m twice? Or some other number?

The sought after result using h and m from above is:

[['aA', 'aA', 'bB', 'bB'],
['aA', 'aB', 'bA', 'bB'],
['aB', 'aB', 'bA', 'bA']]

(the order of the results does not matter i.e. ['aA', 'aA', 'bB', 'bB']
and ['aA', 'bB', 'aA', 'bB'] are considered the same)

This is achieved by the code below, this however needs to go through all
possible combinations (faculty of len(h)) and rule out duplicates as
they occur and this is too much if for example len(h) is 16.

I don't understand this requirement. In the example above, you don't rule
out duplicates. Both 'aA' and 'bB' are duplicated. What duplicates are
you ruling out?

 

[Manuel Pégourié-Gonnard]

Steven D'Aprano scripsit :

I don't understand this requirement. In the example above, you don't rule
out duplicates. Both 'aA' and 'bB' are duplicated. What duplicates are
you ruling out?

I think the requirement is that r != r[j] as soon as i != j, if r is
the resulting list of lists. (As opposed to having r[j] != r[k] for all i
and j != k.)

 

[Ian Kelly]

I don't understand this requirement. In the example above, you don't rule
out duplicates. Both 'aA' and 'bB' are duplicated. What duplicates are
you ruling out?

Duplicate multisets, not duplicate strings.

I'll take a crack at this problem sometime later, but right now I
don't have the time.