从子列表中检索所有可能的升序整数组合 [英] Retrieve all possible combinations of ascending integers from sublists

问题描述

我有包含子列表的列表。从这些列表中，我想检索升序的所有整数组合。此外，子列表的顺序也很重要(参见预期产出)。

当函数也返回整数本身(请参阅预期输出中的可选子列表)时，这不是一件坏事。

此外，当子列表有多个值时，我还想将它们视为单独的组合。这些值不能同时出现(请参见示例3)。

example_list = [[1], [0], [4], [2]]
get_ascending_sublist_values(example_list)
>> [[1, 4], [1, 2], [0, 4], [0, 2] (optional: [1], [0], [4], [2])]

example_list2 = [[1], [0], [4], [2], [5]]
get_ascending_sublist_values(example_list2)
>> [[1, 4, 5], [1, 2, 5], [0, 4, 5], [0, 2, 5], [1, 4], [1, 2], [0, 4], [0, 2], [0, 5], [(optional: [1], [0], [4], [2], [5])]

example_list3 = [[0], [1, 4], [2]]
get_ascending_sublist_values(example_list3)
>> [[0, 1, 2], [0, 1], [0, 4], [0, 2], [1, 2], (optional: [1], [0], [4], [2])]

推荐答案

使用itertools.combinations和itertools.product。这不是一个有效的解决方案，因为这不是必需的。要提高效率(即使用回溯)将需要相当多的工作，而且理论上仍不能低于o(2^n)。

from itertools import combinations
from itertools import product


def get_ascending_sublist_values(a):
    filtered = set()
    for comb_length in range(2, len(a)+1):
        combs = combinations(a, comb_length)

        results = []
        for comb in combs:
            for i in range(len(comb) - 1):
                prods = product(*comb)
                for prod in prods:
                    if sorted(prod) == list(prod):
                        results.append(tuple(sorted(prod)))

        for r in results:
            filtered.add(r)

    print(filtered)


a1 = [[1], [0], [4], [2]]
a2 = [[1], [0], [4], [2], [5]]
a3 = [[0], [1, 4], [2]]


get_ascending_sublist_values(a1)
print("----------")
get_ascending_sublist_values(a2)
print("----------")
get_ascending_sublist_values(a3)

输出：

{(1, 2), (0, 2), (1, 4), (0, 4)}
----------
{(1, 2), (0, 4, 5), (4, 5), (1, 4), (1, 4, 5), (1, 5), (0, 5), (0, 2, 5), (0, 4), (2, 5), (1, 2, 5), (0, 2)}
----------
{(0, 1), (1, 2), (0, 1, 2), (0, 4), (0, 2)}

这篇关于从子列表中检索所有可能的升序整数组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！