On 3 October 2012 20:20, Oscar Benjamin <span dir="ltr"><<a href="mailto:oscar.j.benjamin@gmail.com" target="_blank">oscar.j.benjamin@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">

<div class="im">On 3 October 2012 15:26, Steen Lysgaard <<a href="mailto:boxeakasteen@gmail.com">boxeakasteen@gmail.com</a>> wrote:<br>
</div><div class="im">> Hi,<br>
><br>
> I am looking for a clever way to compute all combinations of two lists. Look<br>
> at this example:<br>
><br>
> h = ['A','A','B','B']<br>
> m = ['a','b']<br>
><br>
> the resulting combinations should be of the same length as h and each<br>
> element in m can be used twice. The sought after result using h and m from<br>
> above is:<br>
><br>
> [['aA', 'aA', 'bB', 'bB'],<br>
>  ['aA', 'aB', 'bA', 'bB'],<br>
>  ['aB', 'aB', 'bA', 'bA']]<br>
><br>
> (the order of the results does not matter i.e. ['aA', 'aA', 'bB', 'bB'] and<br>
> ['aA', 'bB', 'aA', 'bB'] are considered the same)<br>
><br>
> This is achieved by the code below, this however needs to go through all<br>
> possible combinations (faculty of len(h)) and rule out duplicates as they<br>
> occur and this is too much if for example len(h) is 16.<br>
<br>
</div>I'm assuming that len(m) is always 2. Then if len(m) is 16 each<br>
element of h can be used 8 times. If this is not as you intended you<br>
will need to clarify how this problem generalises to other cases.<br></blockquote><div><br></div><div>His code only works when len(m) is half of len(h), so this may not be the right assumption.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


The elements that go with the 'b's are implicitly determined once you<br>
have chosen the elements that go with the 'a's. The problem then is<br>
solved if you choose the elements that go with the 'a's. If we need to<br>
choose say k elements to go with the 'a's the basic problem becomes:<br>
"enumerate over all multisets of size k that are subsets of the<br>
multiset h."<br>
<br>
'''<br>
def submultisets(multiset, subsetsize, stack=None):<br>
    # Enter recursion<br>
    if stack is None:<br>
        multiset = dict((c, multiset.count(c)) for c in set(multiset))<br>
        stack = []<br>
<br>
    c = next(iter(multiset))<br>
<br>
    # End recursion<br>
    if len(multiset) == 1:<br>
        missing = subsetsize - len(stack)<br>
        if multiset[c] >= missing:<br>
            yield stack + missing  * [c]<br>
        return<br>
<br>
    # Continue recursion<br>
    count = multiset.pop(c)<br>
    for n in range(count + 1):<br>
        stack.extend(n * c)<br>
        for result in submultisets(multiset, subsetsize, stack):<br>
            yield result<br>
        del stack[-n:]<br>
    multiset[c] = count<br>
<br>
def uniquecombinations(h, m):<br>
    for ha in submultisets(h, len(h)//2):<br>
        hb = list(h)<br>
        for c in ha:<br>
            hb.remove(c)<br>
        yield [m[0] + a for a in ha] + [m[1] + b for b in hb]<br>
<div class="im"><br>
h = ['A', 'A', 'B', 'B']<br>
m = ['a', 'b']<br>
<br>
</div>for x in uniquecombinations(h, m):<br>
    print(x)<br>
'''<br>
<br>
Output:<br>
<div class="im HOEnZb">['aB', 'aB', 'bA', 'bA']<br>
['aA', 'aB', 'bA', 'bB']<br>
</div><div class="HOEnZb"><div class="h5">['aA', 'aA', 'bB', 'bB']<br></div></div></blockquote></div>