Re: Combinations of lists

Discussion in 'Python' started by Steen Lysgaard, Oct 3, 2012.

  1. 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']
    Steen Lysgaard, Oct 3, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    388
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  2. breal
    Replies:
    14
    Views:
    929
    Steven D'Aprano
    Jan 17, 2008
  3. Ed W.
    Replies:
    1
    Views:
    126
    J├╝rgen Exner
    Oct 22, 2003
  4. Steen Lysgaard

    Combinations of lists

    Steen Lysgaard, Oct 3, 2012, in forum: Python
    Replies:
    4
    Views:
    158
    Ian Kelly
    Oct 3, 2012
  5. Oscar Benjamin

    Re: Combinations of lists

    Oscar Benjamin, Oct 3, 2012, in forum: Python
    Replies:
    0
    Views:
    169
    Oscar Benjamin
    Oct 3, 2012
Loading...

Share This Page