Re: Combinations of lists

[Joshua Landau]

On 4 October 2012 16:12, Steen Lysgaard  wrote:

> 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.
>



 > 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.
>

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 *other* people's
problems].

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.

It runs in a very consistent 55% of the time, but it is longer. Here y'are.

"""Super algorithm."""
>
> from itertools import combinations
> from collections import Counter
>
> def multiples(counter):
> """Counter -> set.
>
> Returns the set of values that occur multiple times.
>  """
> multiples = set()
>
> for item, number in counter.items():
>  if number > 1:
> multiples.add(item)
>
> return multiples
>
> #@profile
> def pairwise_combinations(counter, countermultiples, counterset, length,
> charmap):
> # length is a LIE!
> """Get the permutations of two lists.
>
> Do not call this directly unless you want to hassle yourself.
> Use the wrapper provided, list_permute, instead.
>  """
>
> # We will do the combinations in pairs, as each pair will not have order
> and so
>  # [1, 2, 3, 4] is equivilant to [2, 1, 4, 3] but not [1, 3, 2, 4].
>
> # This means that we get the full permutations without ever filtering.
>
> # Each pair along is a combination.
> # We are combination-ing a set to prevent dulicates.
>  # As the combinations are of length 2, the only ones this will
> # miss are of the type [x, x] (two of the same).
>  # This is accounted for by countermultiples.
> pairs = combinations(counterset, 2)
>
> # Prepend with this
>  length -= 1
> prefix_char = charmap[length]
>
> # There's not reason to recurse, so don't bother with a lot of stuff
>  if not length:
> for p_a, p_b in pairs:
> yield [prefix_char+p_a, prefix_char+p_b]
>  for p in countermultiples:
> yield [prefix_char+p, prefix_char+p]
> return
>
> for p_a, p_b in pairs:
> # Edit scope
> # The recursion wont be able to use items we've already used
>  counter[p_a] -= 1
> counter_p_a = counter[p_a] # Quickref
> if   counter_p_a == 0: counterset.remove(p_a) # None left
>  elif counter_p_a == 1: countermultiples.remove(p_a) # Not plural
>
> counter[p_b] -= 1
> counter_p_b = counter[p_b] # Quickref
>  if   counter_p_b == 0: counterset.remove(p_b) # None left
> elif counter_p_b == 1: countermultiples.remove(p_b) # Not plural
>
> # Recurse
> # Do the same, but for the next pair along
> own_yield = [prefix_char+p_a, prefix_char+p_b]
>  for delegated_yield in pairwise_combinations(counter, countermultiples,
> counterset, length, charmap):
> yield own_yield + delegated_yield
>
> # Reset scope
> counter[p_a] += 1
> if   counter_p_a == 0: counterset.add(p_a)
>  elif counter_p_a == 1: countermultiples.add(p_a)
>
> counter[p_b] += 1
> if   counter_p_b == 0: counterset.add(p_b)
>  elif counter_p_b == 1: countermultiples.add(p_b)
>
>
> # Now do the same for countermultiples
>  # This is not itertools.chain'd because this way
> # is faster and I get to micro-optomize inside
>  for p in countermultiples:
> # Edit scope
> # The recursion wont be able to use items we've already used
>  counter[p] -= 2
> counter_p = counter[p] # Quickref
>
> if   counter_p == 0:
>  counterset.remove(p) # None left
> countermultiples.remove(p) # Must have been in countermultiples, none left
>
> elif counter_p == 1:
> countermultiples.remove(p) # Not plural
>
> # Recurse
>  # Do the same, but for the next pair along
> own_yield = [prefix_char+p, prefix_char+p]
> for delegated_yield in pairwise_combinations(counter, countermultiples,
> counterset, length, charmap):
>  yield own_yield + delegated_yield
>
> # Reset scope
> counter[p] += 2
>
> if   counter_p == 0:
> counterset.add(p)
> countermultiples.add(p)
>
> elif counter_p == 1:
> countermultiples.add(p)
>
> def list_permute(first, second):
> """Get the permutations of two lists as according to what you want, which
> isn't really the
>  permutations of two lists but something close to it. It does what it
> needs to, I think.
>
> This DOES NOT work when  contains duplicates, as the result has
> duplicates. Th

Re: Combinations of lists

[88888 Dihedral]

On Thursday, October 4, 2012 11:12:41 PM UTC+8, Steen Lysgaard wrote:
> 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

If an unique order is defined, then it is trivial to solve this problem
without any recursions. 


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Steen Lysgaard]

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

[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.
*
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[88888 Dihedral]

Oscar Benjamin於 2012年10月4日星期四UTC+8上午4時29分51秒寫道：
> Oscar wrote:
> 
> >>> 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']
> 
> 
> 
> 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.
> 
> >
> 
> > /Steen
> 
> 
> 
> Then you can make the uniquecombinations function recursive. First
> 
> find the elements that go with 'a' then from the remaining elements
> 
> find those that go with 'b', then 'c' and so on.
> 
> 
> 
> Oscar

Lets simplify the problem as follows:

A set of m symbols [0, 1,2,3...m-1] and each symbol can occur
a pecified number of times [(0, k(0)), (1, k(1)), (m-1, k(m-1)].rom a list 
to form a list of (i, k(i)) where  k(i) are  all positive integers.

For example [ (0,3), (1,2), (2, 1), (3, 2)], this is easy to generate 
valid numbers in base m numbers of sum(k(i)) digits.



in the final string.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Oscar Benjamin]

Oscar wrote:
>>> 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']

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.
>
> /Steen

Then you can make the uniquecombinations function recursive. First
find the elements that go with 'a' then from the remaining elements
find those that go with 'b', then 'c' and so on.

Oscar
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Steen Lysgaard]

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

Re: Combinations of lists

[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

Re: Combinations of lists

[Oscar Benjamin]

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.

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']


Oscar
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Joshua Landau]

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.
>
> Can anyone guide me to a better solution?


What lengths can the two lists be?

Is len(h) === 2*len(m), or it it just this time?

Depending on your answer this could be easy or hard ;)
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Manuel Pégourié-Gonnard]

Steven D'Aprano scripsit :

> On Wed, 03 Oct 2012 16:26:43 +0200, Steen Lysgaard wrote:
>
>> 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 don't understand this requirement. In the example above, you don't rule 
> out duplicates. Both 'aA' and 'bB' are duplicated. What duplicates are 
> you ruling out?
>
I think the requirement is that r[i] != r[j] as soon as i != j, if r is
the resulting list of lists. (As opposed to having r[i][j] != r[i][k] for all i
and j != k.)

-- 
Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Steven D'Aprano]

On Wed, 03 Oct 2012 16:26:43 +0200, 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. 

Why twice? What if you had these?

h = ['A', 'A', 'B', 'B', 'C', 'D', 'E', 'E']
m = ['a', 'b', 'c']

Would you still use each element in m twice? Or some other number?



> 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 don't understand this requirement. In the example above, you don't rule 
out duplicates. Both 'aA' and 'bB' are duplicated. What duplicates are 
you ruling out?



-- 
Steven
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Combinations of lists

[Alain Ketterlin]

Steen Lysgaard  writes:

> 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']]

I can't make sense of your explanation, which doesn't seem to match your
example (the result is not of the same size as h).

Here is a way to compute { xh | x in m }, where xh is a list where x is
prepended to each element of h.

result = [ [ x+l for l in h ] for x in m ]

If there is no duplicate in the original lists, then there will be no
duplicate in the result. Is that what you are looking for?

-- Alain.
-- 
http://mail.python.org/mailman/listinfo/python-list

Combinations of lists

[Steen Lysgaard]

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