On 3 October 2012 21:15, Steen Lysgaard <span dir="ltr"><<a href="mailto:boxeakasteen@gmail.com" target="_blank">boxeakasteen@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
thanks for your interest. Sorry for not being completely clear, yes<br>
the length of m will always be half of the length of h.<br></blockquote><div><br></div><div>(Please don't <a href="http://www.catb.org/jargon/html/T/top-post.html">top post</a>)</div><div><br></div><div>I have a solution to this, then.</div>
<div>It's not short <i>or</i> fast, but it's a lot faster than yours.</div><div><br></div><div>But first let me explain the most obvious optimization to your version of the code:</div><div><font face="courier new, monospace"><br>
</font></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><font face="courier new, monospace">combs = set()<br>
<br>for a in permutations(range(len(h)),len(h)):<br> comb = []<br> for i in range(len(h)):<br> comb.append(c[i][a[i]])<br> comb.sort()<br><br> frzn = tuple(comb)<br> if frzn not in combs:<br> combs.add(frzn)</font></blockquote>
<div><br></div><div> 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.</div><div>A set can do the same in O(1). Simplez.</div>
<div><br></div><div><blockquote><font face="courier new, monospace">first = list("AABBCCDDEE")<br>second = list("abcde")<br>import itertools<br>#<br># Generator, so ignoring case convention<br>class force_unique_combinations:<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>def __init__(self, lst, n):<br><span class="Apple-tab-span" style="white-space:pre"> </span>self.cache = set()<br><span class="Apple-tab-span" style="white-space:pre"> </span>self.internal_iter = itertools.combinations(lst, n)<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>def __iter__(self):<br><span class="Apple-tab-span" style="white-space:pre"> </span>return self<br><span class="Apple-tab-span" style="white-space:pre"> </span>def __next__(self):<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>while True:<br><span class="Apple-tab-span" style="white-space:pre"> </span>nxt = next(self.internal_iter)<br><span class="Apple-tab-span" style="white-space:pre"> </span>if not nxt in self.cache:<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>self.cache.add(nxt)<br><span class="Apple-tab-span" style="white-space:pre"> </span>return nxt<br>def combine(first, second):<br><span class="Apple-tab-span" style="white-space:pre"> </span>sletter = second[0]<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>first_combinations = force_unique_combinations(first, 2)<br><span class="Apple-tab-span" style="white-space:pre"> </span>if len(second) == 1:<br><span class="Apple-tab-span" style="white-space:pre"> </span>for combination in first_combinations:<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>yield [sletter+combination[0], sletter+combination[1]]<br><span class="Apple-tab-span" style="white-space:pre"> </span>else:<br><span class="Apple-tab-span" style="white-space:pre"> </span>for combination in first_combinations:<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>first_ = first[:]<br><span class="Apple-tab-span" style="white-space:pre"> </span>first_.remove(combination[0])<br><span class="Apple-tab-span" style="white-space:pre"> </span>first_.remove(combination[1])<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>prefix = [sletter+combination[0], sletter+combination[1]]<br><span class="Apple-tab-span" style="white-space:pre"> </span>for inner in combine(first_, second[1:]):<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>yield prefix + inner<br></font></blockquote><font face="courier new, monospace"><br></font></div><div><font face="arial, helvetica, sans-serif">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.</font></div>
<div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Also, 88888 Dihedral is a bot, or at least pretending like crazy to be one.</b></font></div>
</div>