Combinations of lists

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

  1. 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[a])
    comb.sort()

    if comb not in combs:
    combs.append(comb)

    print combs

    print len(combs)
    Steen Lysgaard, Oct 3, 2012
    #1
    1. Advertising

  2. 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.
    Alain Ketterlin, Oct 3, 2012
    #2
    1. Advertising

  3. 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
    Steven D'Aprano, Oct 3, 2012
    #3
  4. 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 != r[j] as soon as i != j, if r is
    the resulting list of lists. (As opposed to having r[j] != r[k] for all i
    and j != k.)

    --
    Manuel Pégourié-Gonnard - http://people.math.jussieu.fr/~mpg/
    Manuel Pégourié-Gonnard, Oct 3, 2012
    #4
  5. Steen Lysgaard

    Ian Kelly Guest

    On Wed, Oct 3, 2012 at 9:42 AM, Steven D'Aprano
    <> wrote:
    > 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?


    Duplicate multisets, not duplicate strings.

    I'll take a crack at this problem sometime later, but right now I
    don't have the time.
    Ian Kelly, Oct 3, 2012
    #5
    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:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  2. breal
    Replies:
    14
    Views:
    927
    Steven D'Aprano
    Jan 17, 2008
  3. Ed W.
    Replies:
    1
    Views:
    126
    Jürgen Exner
    Oct 22, 2003
  4. Oscar Benjamin

    Re: Combinations of lists

    Oscar Benjamin, Oct 3, 2012, in forum: Python
    Replies:
    0
    Views:
    165
    Oscar Benjamin
    Oct 3, 2012
  5. Steen Lysgaard

    Re: Combinations of lists

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

Share This Page