Re: Combinations of lists

Discussion in 'Python' started by Oscar Benjamin, Oct 3, 2012.

  1. 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
    Oscar Benjamin, 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:
    928
    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:
    156
    Ian Kelly
    Oct 3, 2012
  5. Steen Lysgaard

    Re: Combinations of lists

    Steen Lysgaard, Oct 3, 2012, in forum: Python
    Replies:
    0
    Views:
    172
    Steen Lysgaard
    Oct 3, 2012
Loading...

Share This Page