Combinations of lists

[Joshua Landau]

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

(Please don't top post <http://www.catb.org/jargon/html/T/top-post.html>)

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:
>         combs.add(frzn)


 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:
 self.cache.add(nxt)
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.html>