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.
/Steen 2012/10/3 Joshua Landau <joshua.landau...@gmail.com>: > On 3 October 2012 20:20, Oscar Benjamin <oscar.j.benja...@gmail.com> wrote: >> >> On 3 October 2012 15:26, Steen Lysgaard <boxeakast...@gmail.com> wrote: >> > Hi, >> > >> > I am looking for a clever way to compute all combinations of two lists. >> > Look >> > at this example: >> > >> > h = ['A','A','B','B'] >> > m = ['a','b'] >> > >> > the resulting combinations should be of the same length as h and each >> > element in m can be used twice. The sought after result using h and m >> > from >> > above is: >> > >> > [['aA', 'aA', 'bB', 'bB'], >> > ['aA', 'aB', 'bA', 'bB'], >> > ['aB', 'aB', 'bA', 'bA']] >> > >> > (the order of the results does not matter i.e. ['aA', 'aA', 'bB', 'bB'] >> > and >> > ['aA', 'bB', 'aA', 'bB'] are considered the same) >> > >> > This is achieved by the code below, this however needs to go through all >> > possible combinations (faculty of len(h)) and rule out duplicates as >> > they >> > occur and this is too much if for example len(h) is 16. >> >> I'm assuming that len(m) is always 2. Then if len(m) is 16 each >> element of h can be used 8 times. If this is not as you intended you >> will need to clarify how this problem generalises to other cases. > > > His code only works when len(m) is half of len(h), so this may not be the > right assumption. > >> >> The elements that go with the 'b's are implicitly determined once you >> have chosen the elements that go with the 'a's. The problem then is >> solved if you choose the elements that go with the 'a's. If we need to >> choose say k elements to go with the 'a's the basic problem becomes: >> "enumerate over all multisets of size k that are subsets of the >> multiset h." >> >> ''' >> def submultisets(multiset, subsetsize, stack=None): >> # Enter recursion >> if stack is None: >> multiset = dict((c, multiset.count(c)) for c in set(multiset)) >> stack = [] >> >> c = next(iter(multiset)) >> >> # End recursion >> if len(multiset) == 1: >> missing = subsetsize - len(stack) >> if multiset[c] >= missing: >> yield stack + missing * [c] >> return >> >> # Continue recursion >> count = multiset.pop(c) >> for n in range(count + 1): >> stack.extend(n * c) >> for result in submultisets(multiset, subsetsize, stack): >> yield result >> del stack[-n:] >> multiset[c] = count >> >> def uniquecombinations(h, m): >> for ha in submultisets(h, len(h)//2): >> hb = list(h) >> for c in ha: >> hb.remove(c) >> yield [m[0] + a for a in ha] + [m[1] + b for b in hb] >> >> h = ['A', 'A', 'B', 'B'] >> m = ['a', 'b'] >> >> for x in uniquecombinations(h, m): >> print(x) >> ''' >> >> Output: >> ['aB', 'aB', 'bA', 'bA'] >> ['aA', 'aB', 'bA', 'bB'] >> ['aA', 'aA', 'bB', 'bB'] -- http://mail.python.org/mailman/listinfo/python-list