Priority ordered combinations of a list

Question

First of all, all possible combinations of a list should be generated. It is straightforward problem - thanks to itertools.combinations. Then, the combinations must be ordered according to the following priorities: first element of the original list has the highest priority, second has the second priority and so on. Note that any grouping of lower priorities cannot be higher than any higher priority. Trivial example:

input = ['A', 'B']
output = [['A', 'B'], ['A'], ['B']]

3 elements example:

input = ['A', 'B', 'C']
output = [['A', 'B', 'C'], ['A', 'B'], ['A', 'C'], ['A'], ['B', 'C'], ['B'], ['C']]

Question: Given a list of any elements, how to find the list of all possible combinations ordered by priorities as described above?

the question is clear IMO, they have several examples of inputs and outputs and they thought about using itertools — Chris_Rands, Nov 30 '18 at 22:24

hilberts_drinking_problem · Accepted Answer · 2018-11-30T22:40:06.950

3

Adding an element to a list always increases priority. We can maintain a list of lists and recursively add worst elements first to get the desired order.

cs = ["A", "B", "C"]


def subsets(xs):
    res = [[]]
    for x in xs[::-1]:
        res = [[x] + r for r in res] + res

    return res[:-1]


# [["A", "B", "C"], ["A", "B"], ["A", "C"], ["A"], ["B", "C"], ["B"], ["C"]]

During the execution, res looks as follows:

[[]]
[["C"],[]]
[["B","C"],["B"],["C"],[]]
...

Alternatively, you can rely on itertools.product to get a lazy solution.

from itertools import product


def lazy_subsets(xs):
    for ix in product(*([[True, False]] * len(xs))):
        yield [x for x, b in zip(xs, ix) if b]


res = list(lazy_subsets(cs))[:-1]

Here, each ix is a list of bools that is used as a boolean mask to filter xs. The order in which product yields ix's coincides with the order on subsets of xs that gives priorities to initial elements.

edited Nov 30 '18 at 22:40

answered Nov 30 '18 at 22:28

hilberts_drinking_problem

11,322
3
22
51

I would be happy to hear how to improve this answer. – hilberts_drinking_problem Nov 30 '18 at 22:33
like your itertools.product solution - really concise... – Craig Nov 30 '18 at 23:08
Upvoted! It looks very "pythonic". – Felipe Gutierrez Dec 01 '18 at 01:38

slider · Answer 2 · 2018-11-30T23:11:49.683

You can sort the combinations by a priority function which is defined as a sorted list of original indices of elements of a combination (lower index means higher priority) padded by infinities at the end (since we want to give higher length combinations a chance against lower length combinations):

from itertools import combinations

lst = ['A', 'B', 'C']
index = {l: i for i, l in enumerate(lst)}

def priority(c):
    return sorted([index[x] for x in c]) + [float('inf')] * (len(lst) - len(c))


result = sorted([c for i in range(1, len(lst) + 1) for c in combinations(lst, i)], key=priority)
print(result)
# [('A', 'B', 'C'), ('A', 'B'), ('A', 'C'), ('A',), ('B', 'C'), ('B',), ('C',)]

score 0 · Answer 3 · answered Nov 30 '18 at 23:00

A little clunky, but this works using itertools.combinations...

import itertools

def iter(string):
    raw_result = []
    result = []
    for i in range(len(string), -1, -1):
        for y in itertools.combinations(string, i):
            if len(y) > 0:
                raw_result.append(list(y))
    for s in string:
        for bit in raw_result:
            if s == bit[0]:
                result.append(bit)
    return result
print(iter('ABCD'))

Priority ordered combinations of a list

3 Answers3