CODEWITHSUNDEEP
pythoncombinationspermutation
jef
jef

Reputation: 4083

Find combinations with arrays and a combination pattern

I have arrays such as these, and each pattern designates a combination shape with each number representing the size of the combination.

I also have a char-valued list like below. len(chars) equals the sum of the upper array's value.

chars = ['A', 'B', 'C', 'D']

I want to find all combinations of chars following a given pattern. For example, for pattern 1, 4C2 * 2C1 * 1C1 is the number of combinations.

[['A', 'B'], ['C'], ['D']]
[['A', 'B'], ['D'], ['C']]
[['A', 'C'], ['B'], ['D']]
[['A', 'C'], ['D'], ['B']]
[['A', 'D'], ['B'], ['C']]
[['A', 'D'], ['C'], ['B']]
...

But I don't know how to create such combination arrays. Of course I know there are a lot of useful functions for combinations in python. But I don't know how to use them to create a combination array of combinations.

EDITED

I'm so sorry my explanation is confusing. I show a simple example.

Then, the result should be like below. So first dimension should be permutation, but second dimension should be combination.

Upvotes: 2

Views: 485

Answers (1)

niemmi
niemmi

Reputation: 17263

You can use recursive function that takes the first number in pattern and generates all the combinations of that length from remaining items. Then recurse with remaining pattern & items and generated prefix. Once you have consumed all the numbers in pattern just yield the prefix all the way to caller:

from itertools import combinations

pattern = [2, 1, 1]
chars = ['A', 'B', 'C', 'D']

def patterns(shape, items, prefix=None):
    if not shape:
        yield prefix
        return

    prefix = prefix or []
    for comb in combinations(items, shape[0]):
        child_items = items[:]
        for char in comb:
            child_items.remove(char)
        yield from patterns(shape[1:], child_items, prefix + [comb])

for pat in patterns(pattern, chars):
    print(pat)

Output:

[('A', 'B'), ('C',), ('D',)]
[('A', 'B'), ('D',), ('C',)]
[('A', 'C'), ('B',), ('D',)]
[('A', 'C'), ('D',), ('B',)]
[('A', 'D'), ('B',), ('C',)]
[('A', 'D'), ('C',), ('B',)]
[('B', 'C'), ('A',), ('D',)]
[('B', 'C'), ('D',), ('A',)]
[('B', 'D'), ('A',), ('C',)]
[('B', 'D'), ('C',), ('A',)]
[('C', 'D'), ('A',), ('B',)]
[('C', 'D'), ('B',), ('A',)]

Note that above works only with Python 3 since it's using yield from.

Upvotes: 1

Related Questions