列表的优先排序组合

Question

首先，应生成列表的所有可能组合。这是一个简单的问题 - 感谢itertools.combinations。然后，必须根据以下优先级对组合进行排序：原始列表的第一个元素具有最高优先级，第二个具有第二个优先级，依此类推。请注意，任何较低优先级的分组都不能高于任何较高优先级。简单的例子：input = ['A', 'B']output = [['A', 'B'], ['A'], ['B']]3个元素示例：input = ['A', 'B', 'C']output = [['A', 'B', 'C'], ['A', 'B'], ['A', 'C'], ['A'], ['B', 'C'], ['B'], ['C']]问题：给定任何元素的列表，如何找到按优先级排序的所有可能组合的列表，如上所述？

Answer 1

将元素添加到列表总是会增加优先级。我们可以维护一个列表列表并首先递归地添加最差的元素以获得所需的顺序。

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"]]

在执行过程中，res看起来如下：

[[]]

[["C"],[]]

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

...

或者，您可以依靠itertools.product获得一个懒惰的解决方案。

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]

这里，每个ix都是一个bools列表，用作过滤的布尔掩码xs。的顺序product的产率ix的一致上的子集的顺序xs给出到初始元素的优先级。

Answer 2

您可以通过优先级函数对组合进行排序，该函数被定义为组合元素的原始索引的排序列表（较低的索引意味着更高的优先级）在最后用无穷大填充（因为我们希望给更高的长度组合一个机会对抗更低的长度组合）：

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',)]

Answer 3

有点笨重，但这可以使用 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'))