On 4 October 2012 16:12, 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">
2012/10/4 Joshua Landau <<a href="mailto:joshua.landau.ws@gmail.com" target="_blank">joshua.landau.ws@gmail.com</a>>:<br>
<div><div>> On 3 October 2012 21:15, Steen Lysgaard <<a href="mailto:boxeakasteen@gmail.com" target="_blank">boxeakasteen@gmail.com</a>> wrote:<br>
>><br>
>> 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>
><br>
><br>
> (Please don't top post)<br>
><br>
> I have a solution to this, then.<br>
> It's not short or fast, but it's a lot faster than yours.<br></div></div></blockquote><div> </div><div><snip> </div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div>
> This is quite naive, because I don't know how to properly implement<br>
> force_unique_combinations, but it runs. I hope this is right. If you need<br>
> significantly more speed your best chance is probably Cython or C, although<br>
> I don't doubt 10x more speed may well be possible from within Python.<br>
><br>
><br>
> Also, 88888 Dihedral is a bot, or at least pretending like crazy to be one.<br>
<br>
</div></div>Great, I've now got a solution much faster than what I could come up with.<br>
Thanks to the both of you.<br></blockquote><div><br></div><div>Don't use it though :P. I've something better, now I've used a few sanity-points up [it's much more interesting to solve <i>other</i> people's problems].</div>
<div><br></div><div>Please note that my implementations (old and new) return duplicates when the second list contains duplicates. It's fixable, but I'll only bother if you need it fixed.</div><div> </div><div>It runs in a very consistent 55% of the time, but it is longer. Here y'are.</div>
<div><br></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">"""Super algorithm."""<br>
<br>from itertools import combinations<br>from collections import Counter<br><br>def multiples(counter):<br><span class="Apple-tab-span" style="white-space:pre"> </span>"""Counter -> set.<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>Returns the set of values that occur multiple times.<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>"""<br><span class="Apple-tab-span" style="white-space:pre"> </span>multiples = set()<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>for item, number in counter.items():<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>if number > 1:<br><span class="Apple-tab-span" style="white-space:pre"> </span>multiples.add(item)<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>return multiples<br>
<br>#@profile<br>def pairwise_combinations(counter, countermultiples, counterset, length, charmap):<br><span class="Apple-tab-span" style="white-space:pre"> </span># length is a LIE!<br><span class="Apple-tab-span" style="white-space:pre"> </span>"""Get the permutations of two lists.<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>Do not call this directly unless you want to hassle yourself.<br><span class="Apple-tab-span" style="white-space:pre"> </span>Use the wrapper provided, list_permute, instead.<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>"""<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># We will do the combinations in pairs, as each pair will not have order and so<br>
<span class="Apple-tab-span" style="white-space:pre"> </span># [1, 2, 3, 4] is equivilant to [2, 1, 4, 3] but not [1, 3, 2, 4].<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># This means that we get the full permutations without ever filtering.<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span># Each pair along is a combination.<br><span class="Apple-tab-span" style="white-space:pre"> </span># We are combination-ing a set to prevent dulicates.<br>
<span class="Apple-tab-span" style="white-space:pre"> </span># As the combinations are of length 2, the only ones this will<br><span class="Apple-tab-span" style="white-space:pre"> </span># miss are of the type [x, x] (two of the same).<br>
<span class="Apple-tab-span" style="white-space:pre"> </span># This is accounted for by countermultiples.<br><span class="Apple-tab-span" style="white-space:pre"> </span>pairs = combinations(counterset, 2)<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># Prepend with this<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>length -= 1<br><span class="Apple-tab-span" style="white-space:pre"> </span>prefix_char = charmap[length]<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># There's not reason to recurse, so don't bother with a lot of stuff<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>if not length:<br><span class="Apple-tab-span" style="white-space:pre"> </span>for p_a, p_b in pairs:<br><span class="Apple-tab-span" style="white-space:pre"> </span>yield [prefix_char+p_a, prefix_char+p_b]<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>for p in countermultiples:<br><span class="Apple-tab-span" style="white-space:pre"> </span>yield [prefix_char+p, prefix_char+p]<br><span class="Apple-tab-span" style="white-space:pre"> </span>return<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>for p_a, p_b in pairs:<br><span class="Apple-tab-span" style="white-space:pre"> </span># Edit scope<br><span class="Apple-tab-span" style="white-space:pre"> </span># The recursion wont be able to use items we've already used<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>counter[p_a] -= 1<br><span class="Apple-tab-span" style="white-space:pre"> </span>counter_p_a = counter[p_a] # Quickref<br><span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p_a == 0: counterset.remove(p_a) # None left<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p_a == 1: countermultiples.remove(p_a) # Not plural<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>counter[p_b] -= 1<br><span class="Apple-tab-span" style="white-space:pre"> </span>counter_p_b = counter[p_b] # Quickref<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p_b == 0: counterset.remove(p_b) # None left<br><span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p_b == 1: countermultiples.remove(p_b) # Not plural<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span># Recurse<br><span class="Apple-tab-span" style="white-space:pre"> </span># Do the same, but for the next pair along<br><span class="Apple-tab-span" style="white-space:pre"> </span>own_yield = [prefix_char+p_a, prefix_char+p_b]<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>for delegated_yield in pairwise_combinations(counter, countermultiples, counterset, length, charmap):<br><span class="Apple-tab-span" style="white-space:pre"> </span>yield own_yield + delegated_yield<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span># Reset scope<br><span class="Apple-tab-span" style="white-space:pre"> </span>counter[p_a] += 1<br><span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p_a == 0: counterset.add(p_a)<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p_a == 1: countermultiples.add(p_a)<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>counter[p_b] += 1<br><span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p_b == 0: counterset.add(p_b)<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p_b == 1: countermultiples.add(p_b)<br><br><br><span class="Apple-tab-span" style="white-space:pre"> </span># Now do the same for countermultiples<br>
<span class="Apple-tab-span" style="white-space:pre"> </span># This is not itertools.chain'd because this way<br><span class="Apple-tab-span" style="white-space:pre"> </span># is faster and I get to micro-optomize inside<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>for p in countermultiples:<br><span class="Apple-tab-span" style="white-space:pre"> </span># Edit scope<br><span class="Apple-tab-span" style="white-space:pre"> </span># The recursion wont be able to use items we've already used<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>counter[p] -= 2<br><span class="Apple-tab-span" style="white-space:pre"> </span>counter_p = counter[p] # Quickref<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p == 0:<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>counterset.remove(p) # None left<br><span class="Apple-tab-span" style="white-space:pre"> </span>countermultiples.remove(p) # Must have been in countermultiples, none left<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p == 1:<br><span class="Apple-tab-span" style="white-space:pre"> </span>countermultiples.remove(p) # Not plural<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># Recurse<br>
<span class="Apple-tab-span" style="white-space:pre"> </span># Do the same, but for the next pair along<br><span class="Apple-tab-span" style="white-space:pre"> </span>own_yield = [prefix_char+p, prefix_char+p]<br><span class="Apple-tab-span" style="white-space:pre"> </span>for delegated_yield in pairwise_combinations(counter, countermultiples, counterset, length, charmap):<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>yield own_yield + delegated_yield<br><br><span class="Apple-tab-span" style="white-space:pre"> </span># Reset scope<br><span class="Apple-tab-span" style="white-space:pre"> </span>counter[p] += 2<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>if counter_p == 0:<br><span class="Apple-tab-span" style="white-space:pre"> </span>counterset.add(p)<br><span class="Apple-tab-span" style="white-space:pre"> </span>countermultiples.add(p)<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>elif counter_p == 1:<br><span class="Apple-tab-span" style="white-space:pre"> </span>countermultiples.add(p)<br><br>def list_permute(first, second):<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>"""Get the permutations of two lists as according to what you want, which isn't really the<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>permutations of two lists but something close to it. It does what it needs to, I think.<br><br><span class="Apple-tab-span" style="white-space:pre"> </span>This DOES NOT work when <second> contains duplicates, as the result has duplicates. The other<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>of mine does not work either. If this is a problem, it should be fixable: sort <second><br><span class="Apple-tab-span" style="white-space:pre"> </span>and when you encounter the duplicates generate in groups bigger than 2. You cannot do as above<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>for pairs, so an intermittent filtering method will work best. I won't implement this if it's<br><span class="Apple-tab-span" style="white-space:pre"> </span>unneeded, though.<br>
<br><span class="Apple-tab-span" style="white-space:pre"> </span>This runs in 55% of the time of my previous one, with over twice the number of lines.<br><span class="Apple-tab-span" style="white-space:pre"> </span>W007! Lines!<br>
<span class="Apple-tab-span" style="white-space:pre"> </span>"""<br><span class="Apple-tab-span" style="white-space:pre"> </span>count = Counter(first)<br><span class="Apple-tab-span" style="white-space:pre"> </span>return pairwise_combinations(count, multiples(count), set(count), len(first)//2, list(reversed(second)))<br>
<br># TEST #<br><br>second = "abcde"<br>first = sorted((second+second).upper())<br><br>n = 0<br>for _ in list_permute(first, second): n += 1<br>print(n)</font></blockquote><div><br></div><div>I release this under whatever permissive licence you want.</div>
</div>