# Combinations of lists

Joshua Landau joshua.landau.ws at gmail.com
Thu Oct 4 00:35:02 CEST 2012

```On 3 October 2012 21:15, Steen Lysgaard <boxeakasteen at gmail.com> wrote:

> Hi,
>
> thanks for your interest. Sorry for not being completely clear, yes
> the length of m will always be half of the length of h.
>

I have a solution to this, then.
It's not short *or* fast, but it's a lot faster than yours.

But first let me explain the most obvious optimization to your version of
the code:

combs = set()
>
> for a in permutations(range(len(h)),len(h)):
>     comb = []
>     for i in range(len(h)):
>         comb.append(c[i][a[i]])
>     comb.sort()
>
>     frzn = tuple(comb)
>     if frzn not in combs:

What I have done here is make your "combs" a set. This helps because you
are searching inside it and that is an O(N) operation... for lists.
A set can do the same in O(1). Simplez.

first  = list("AABBCCDDEE")
second = list("abcde")
import itertools
#
# Generator, so ignoring case convention
class force_unique_combinations:
def __init__(self, lst, n):
self.cache = set()
self.internal_iter = itertools.combinations(lst, n)
def __iter__(self):
return self
def __next__(self):
while True:
nxt = next(self.internal_iter)
if not nxt in self.cache:
return nxt
def combine(first, second):
sletter = second[0]
first_combinations = force_unique_combinations(first, 2)
if len(second) == 1:
for combination in first_combinations:
yield [sletter+combination[0], sletter+combination[1]]
else:
for combination in first_combinations:
first_ = first[:]
first_.remove(combination[0])
first_.remove(combination[1])
prefix = [sletter+combination[0], sletter+combination[1]]
for inner in combine(first_, second[1:]):
yield prefix + inner

This is quite naive, because I don't know how to properly implement
force_unique_combinations, but it runs. I hope this is right. If you need
significantly more speed your best chance is probably Cython or C, although
I don't doubt 10x more speed may well be possible from within Python.

*Also, 88888 Dihedral is a bot, or at least pretending like crazy to be one.
*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20121003/812745ed/attachment-0001.html>
```