Python:将4个列表中的元素组合起来，跳过其中包含重复项的列表的组合

Question

我有点失落..。我有以下数据集作为输入(通常多一个类别，以简化现在的三个)：

category = 
{"A" :[1002, 1004,1003,1008], 
"B": [1002, 1004,1009], 
"C":[1002,1003,1006,1005]}

作为输出，我希望元素的所有可能组合都受到限制，即只有在元素不在其他类别时才能完成组合。例如，1002属于所有类别，因此不可能进行组合。1004在A和B中，所以它可以与C中的一个元素组合，它在A和B中没有重复，或者什么都没有，等等。

此示例的输出应该是：

Out: [[1002],[1003],[1008],[1009],[1004], [1006],[1006,1008,1009],[1005,1008,1009],[1003,1009][1005,1008],[1004,1005],[1008,1006],[1009,1008],[1005,1009]]

*我希望我没有忘记任何密码，请让我知道，我更新

也许有人能帮我，

现在我已经尝试了几个小时，首先合并所有元素，对输出进行排序，并删除列表和子列表中的重复项。但现在我不知道如何进一步过滤掉我仍然“错误的组合”。所以我想这是错误的方式..。

这是我的起点..。

def get_list_of_lists(list_of_tuples):
    list_of_lists = []                                                          
    for tuple in list_of_tuples:
        list_of_lists.append(list(tuple))

    return list_of_lists

def rem_dup(lis):
    y, s = [], set()
    for t in lis:
        w = tuple(sorted(t)) if isinstance(t, list) else t
        if not w in s:
            y.append(t)
            s.add(w)
    return y


category = {"A" :[3001,1002,1001,8002,2002], "B": [4002,7001,3001,1002,2002], "C":[4002,4001,1002,5001], "D":[4001,1002,1001,2002]}
s = [category["A"], category["B"], category["C"], category["D"]]
s1=list(itertools.product(*s))
s2 = get_list_of_lists(s1)
for sublists in s2:
    sublists.sort()
inp = s2
out = [rem_dup(i) if isinstance(i, list) else i for i in rem_dup(inp)] 
new_out = []
for part in out:
    if part not in new_out:
        new_out.append(part)
out = new_out

Answer 1

我假设可以忽略类别和顺序的标识(结果组合或每个组合中的数字)。

lst = [{1002, 1004, 1003, 1008},
       {1002, 1004, 1009},
       {1002, 1003, 1006, 1005}]

mask = dict()
for s in lst:
    for num in s:
        mask[num] = mask.get(num, set()) | s

def get_combs(lst):
    if lst == []:
        return [[]]
    output = []
    output += get_combs(lst[1:]) # not picking any number at this category
    for num in lst[0]:
        sublst_masked = [s - mask[num] for s in lst[1:]]
        output += [[num] + comb for comb in get_combs(sublst_masked)]
    return output

output = get_combs(lst)
# print(output) # this might have duplicates
output = set(tuple(sorted(l)) for l in output)
print(output) # {(1002,), (1008,), (1005,), (1006, 1009), (1006, 1008, 1009), (1004, 1006), (1004,), (1006, 1008), (1008, 1009), (1005, 1008, 1009), (1005, 1009), (1009,), (1003, 1009), (1004, 1005), (1006,), (1005, 1008), (1003,), ()}

注意，我更改了输入的数据结构；现在，它是一个集合列表，没有类别名称。

其思想是为输入中出现的每个数字定义一个“掩码”；例如，mask[1003]输出{1002, 1003, 1004, 1005, 1006, 1008}，这意味着在包含1003的数字列表中，这些数字不会出现。因此，例如，如果您在第一个类别中选择了1003，那么您将只从第二个类别中选择数字1009 (它不在掩码中)(或者没有)。一旦您选择了1003和1009，那么在第三个类别中，每个数字都在对应于1003或1009的掩码中，因此您不能从第三个类别中选择任何数字。因此，[1003, 1009]是解决方案中的组合之一，而它的超级列表中进一步包含第三类数字的列表则不是。

对于每个类别，您可能需要一个(嵌套的) for循环来从类别中选择一个数字，但我使用递归函数get_combs()实现了它，用于这个循环、拾取和掩蔽过程。我选择使用递归函数，因为我不知道如何将嵌套循环的深度概括为任意数量的类别。

请验证我在代码最后一行提供的输出。(我已经检查了示例输出是该输出的子集。)结果包含一个空元组，对应于在每个类别中不选择数字。但如果有必要的话，你当然可以把它移除。

Answer 2

您可以使用itertools.product获取所有选项的笛卡尔管道，然后将其简化为非重复选项：

>>> import itertools
>>> list(map(set,itertools.product(*category.values())))

[{1002}, {1002, 1003}, {1002, 1006}, ..., {1008, 1009, 1005}]

为了进一步删除元素，由于组中有两个或更多相同的元素，例如{1002, 1004, 1003}和{1004, 1002, 1003}，会重复这些元素。

>>> import numpy as np
>>> np.unique(list(map(lambda y: list(set(sorted(y))),itertools.product(*category.values()))))
array([list([1002]), list([1002, 1003]), ...,
       list([1009, 1004, 1006])], dtype=object)