On 3 October 2012 21:15, Steen Lysgaard <boxeakast...@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. *
-- http://mail.python.org/mailman/listinfo/python-list
