Re: Combinations of lists
2012/10/4 Joshua Landau :
> On 3 October 2012 21:15, Steen Lysgaard 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, 8 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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Combinations of lists
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 : > On 3 October 2012 20:20, Oscar Benjamin wrote: >> >> On 3 October 2012 15:26, Steen Lysgaard 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
Combinations of lists
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. Can anyone guide me to a better solution? Thanks, Steen h = ['A','A','B','B'] m = ['a','b'] c = [] for i in h: c.append([]) for j in m: c[-1].append(j+i) c[-1].append(j+i) combs = [] for a in permutations(range(len(h)),len(h)): comb = [] for i in range(len(h)): comb.append(c[i][a[i]]) comb.sort() if comb not in combs: combs.append(comb) print combs print len(combs) -- http://mail.python.org/mailman/listinfo/python-list
