时间戳

首页 > 解决方案 > 如何找到所有可能的方法来组合列表中的项目而不重复？

python - 如何找到所有可能的方法来组合列表中的项目而不重复？

问题描述

我有六个类别：A、B、C、D、E 和 F。

我想找出所有可以组合类别的独特方式，而无需重复。

例如，如果我结合前三个类别，我将得到 A、A、A、B、C、D。如果我结合 B、C、D、E，我将得到 A、B、B、B、B、 C。

我试过迭代工具。itertools.product 很接近，但有很多重复。例如，我得到 A、B、A、A、C、D，但我也得到 B、A、B、B、D、C，这在我的情况下是重复的。顺序很重要，替换很重要，计数很重要，但性格并不重要。

标签： pythonlistpermutation

解决方案

由于您只有 6 个类别，您可以使用 itertools.product 然后根据您的标准过滤您的结果。

您的示例有些令人困惑，因为我不确定您如何从不包含“D”的前三个类别“ABC”中获得“AAABCD”，或者如何通过组合不包含“D”的“BCDEI”获得“ABBBBC”包含“A”。但是，假设您想要获得长度为 6 的“ABCDEF”的某个子集的所有唯一组合，直到符号替换，您可以这样做。

from itertools import product

CATEGORIES = 'ABCDEF'

def combinations(cats):
    # use itertools to get all combinations 
    all_combs = product(cats,repeat=len(CATEGORIES))
    valid_combs = set()

    # For every possible combination find the order in which the characters appear
    for s in all_combs:
        s = ''.join(s)
        order = []
        for c in s:
            if c not in order: 
                order.append(c)

        # replace the character by ones following a set predetermined order
        for i,c in enumerate(order):
            replace_char = CATEGORIES[i].lower()
            s = s.replace(c, replace_char)

        # add to set to remove duplicates
        s = s.upper()
        valid_combs.add(s)
    return list(valid_combs)

用法

combinations('AB') 
['ABABBB', 'ABABBA', 'AABBBB', 'ABAABB', 'ABBAAA', 'AABAAA', 'AABABB', 'AAABAB', 'AABABA', 'AABAAB', 'ABAAAB', 'AABBAB', 'AAAAAB', 'ABBAAB', 'ABBABA', 'ABBABB', 'AAAABA', 'ABAAAA', 'AAABAA', 'ABAABA', 'ABBBAB', 'AAABBB', 'ABBBBA', 'AAABBA', 'AABBAA', 'ABABAA', 'AAAAAA', 'ABBBBB', 'ABABAB', 'ABBBAA', 'AABBBA', 'AAAABB']

这样做的基本原理是，如果 'ABAACD' 和 'BABBDC' 属于同一个等价类，则字符按顺序出现的成员是该等价类的唯一代表。

虽然这不是很有效，因此对于更大的类别列表，您可能需要直接构建列表。

推荐阅读