On Thursday, October 4, 2012 11:12:41 PM UTC+8, Steen Lysgaard wrote: > 2012/10/4 Joshua Landau <joshua.landau...@gmail.com>: > > > 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) > > > > > > 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. > > > > Great, I've now got a solution much faster than what I could come up with. > > Thanks to the both of you. > > And a good spot on 88... I could not for my life understand what he > > (it) had written. > > > > /Steen
If an unique order is defined, then it is trivial to solve this problem without any recursions. -- http://mail.python.org/mailman/listinfo/python-list