# Combinations of lists

Discussion in 'Python' started by Steen Lysgaard, Oct 3, 2012.

1. ### Steen LysgaardGuest

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)

Steen Lysgaard, Oct 3, 2012

2. ### Alain KetterlinGuest

Steen Lysgaard <> writes:

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

Alain Ketterlin, Oct 3, 2012

3. ### Steven D'ApranoGuest

On Wed, 03 Oct 2012 16:26:43 +0200, Steen Lysgaard wrote:

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

--
Steven

Steven D'Aprano, Oct 3, 2012
4. ### Manuel Pégourié-GonnardGuest

Steven D'Aprano scripsit :

> On Wed, 03 Oct 2012 16:26:43 +0200, Steen Lysgaard wrote:
>
>> 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?
>

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

--
Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/

Manuel Pégourié-Gonnard, Oct 3, 2012
5. ### Ian KellyGuest

On Wed, Oct 3, 2012 at 9:42 AM, Steven D'Aprano
<> wrote:
> 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.

Ian Kelly, Oct 3, 2012