获取 K 组 N 个成员和 L 组 M 个成员的组合列表。

Question

在Python中，给定可能成员列表g，对于k组n个成员和l组m个成员的所有组合，最好的方法是什么？例如，给定以下元素列表：

g = ["A", "B", "C", "D", "E", "F", "G"]

我希望能够得到一个列表li，其中包含所有2个(=k) 2个(=n)组合和1个(=l) 3个(=m)组合的组合方式。

[["AB", "CD", "EFG"],
 ["AC", "BD", "EFG"],
 ["AD", "CB", "EFG"],
 ["AE", "CD", "BFG"],
 ["AF", "CD", "BEG"],... ]

1. 每个组中不允许有元素的重复出现（相当于说：对于每个不同的组合，我希望每个不同的元素在所有组中只出现一次）。

   例如，["AB", "AD", "EFG"] 不是有效的组合，因为它包含元素 A 在所有组中重复出现。

2. 不允许组内存在不同的排列方式；

   例如，["AB", "CD", "EFG"] 不应以 ["BA", "DC", "EGF"] 的形式重复出现。

3. 如果任何一个组合出现在 k-groups 中，则不希望该组合在 k-groups 中的 l-groups 也重复出现（对于 l-groups 同样如此）。

   例如，如果 ["AB", "CD", "EFG"] 出现，则不应再出现 [ "CD", "AB", "EFG"]。

清楚地说，我只关心组将完全适配要使用的所有元素的情况 (g)：

例如，2x2 + 1x3 == 7 == len(["A", "B", "C", "D", "E", "F", "G"])，1x2 + 1x3 == 5 == len(["A", "B", "C", "D", "E"])。

---

我可以使用 Python 的排列函数 ，并在每个排列中将元素分成 k 组的 n 个和 l 组的 m 个，但对于更多元素，我将有很多不必要的迭代。

- Bentley4

---

你能在一个字符串中复制元素吗？例如，["AB", "BC", "EFE"] 是合法的吗？ - Prune

需要修正您的发布吗？像["AB", "BC", "EFG"]这样的一些示例中已经重复了 B 和 C。 - Prune

已修复！感谢您的提醒。 - Bentley4

根据您的澄清，我发布的答案是错误的：它在组之间发出重复项。这个问题并不像一开始看起来那么简单：每个组都必须是词典中的组合，而且您需要所有互斥排列组合。 - Prune

你想要 ["AB", "CD", "EFG"] 和 ["CD", "AB", "EFG"] 两者都得到还是只需要其中一个？ - rici

Answer 1

编辑：代码已经修改以满足更新的要求（规则3）。

代码：

import itertools as it


def unique_group(iterable, k, n):
    """Return an iterator, comprising groups of size `k` with combinations of size `n`."""
    # Build separate combinations of `n` characters
    groups = ("".join(i) for i in it.combinations(iterable, n))    # 'AB', 'AC', 'AD', ...

    # Build unique groups of `k` by keeping the longest sets of characters
    return (i for i in it.combinations(groups, k) 
                if len(set("".join(i))) == sum((map(len, i))))     # ('AB', 'CD'), ('AB', 'CE'), ... 


def combined(groups1, groups2):
    """Return an iterator with unique combinations of groups (k and l)."""
    # Build a unique cartesian product of groups `k` and `l`, filtering non-disjoints
    return (i[0] + i[1]
               for i in it.product(groups1, groups2) 
               if set("".join(i[0])).isdisjoint(set("".join(i[-1]))))


iterable = "ABCDEFG"
g1 = unique_group(iterable, 2, 2)
g2 = unique_group(iterable, 1, 3)
result = list(combined(g1, g2))
print(len(result))
result

输出：

105

[('AB', 'CD', 'EFG'),
 ('AB', 'CE', 'DFG'),
 ...,
 ('BC', 'AD', 'EFG'),
 ('BC', 'AE', 'DFG'),
 ...,
]

在演示文稿中，您可以找到详细信息和见解。

- pylang

---

我认为你已经接近成功了。例如，使用iterable =“ABCDE”，g1 = unique_group（iterable，1，2）和g2 = unique_group（iterable，1，3）尝试会得到以下结果： [('AD'，'BCE')，（'AE'，'BCD'），（'BC'，'ADE'），（'BD'，'ACE'），（'BE'，'ACD'），（'CD'，'ABE'），（'CE'，'ABD'），（'DE'，'ABC')]。例如，缺少组合（'AB'，'CDE'）和（'AC'，'BDE'）。 - Bentley4

有了你的新输入，我得到了所有这些组合（一个包含10个项目的列表）。 - pylang

Answer 2

编辑：经过澄清，我添加了一行应该完成解决方案...

这个怎么样，它使用了几个itertools和flatten recipe。无论如何，我认为你想要使用itertools.combinations：

from itertools import combinations, chain, product

def flatten(listOfLists):
    "Flatten one level of nesting"
    return chain.from_iterable(listOfLists)

lico = lambda li,x: list( combinations(li,x) ) 
def get_funky_groups( elements, k,n,l,m ):     
    kn = lico( lico(elements,n),k)  # k groups of n elements
    lm = lico( lico( elements,m), l)  # l groups of m elements
    results =  [map( lambda x: "".join(x), flatten(r)) for r in product(kn, lm)]
    # added this line so that only each element was used once.. 
    return [ r for r in results if len(set( flatten( r))) == len(g) ]

针对您的示例列表，这将产生105个结果。

In [3]: g = ["A", "B", "C", "D", "E", "F", "G"]

In [4]: results = get_funky_groups(g, 2,2,1,3)

In [5]: results[:10]
Out[5]: 
[['AB', 'CD', 'EFG'],
 ['AB', 'CE', 'DFG'],
 ['AB', 'CF', 'DEG'],
 ['AB', 'CG', 'DEF'],
 ['AB', 'DE', 'CFG'],
 ['AB', 'DF', 'CEG'],
 ['AB', 'DG', 'CEF'],
 ['AB', 'EF', 'CDG'],
 ['AB', 'EG', 'CDF'],
 ['AB', 'FG', 'CDE']]

In [6]: len( results) 
Out[6]: 105

In [7]: g = ["A", "B", "C", "D", "E"]

In [8]: results = get_funky_groups(g, 1,2,1,3)

In [9]: results
Out[9]: 
[['AB', 'CDE'],
 ['AC', 'BDE'],
 ['AD', 'BCE'],
 ['AE', 'BCD'],
 ['BC', 'ADE'],
 ['BD', 'ACE'],
 ['BE', 'ACD'],
 ['CD', 'ABE'],
 ['CE', 'ABD'],
 ['DE', 'ABC']]

也许你不想要一个基于字符串元素的答案。

def get_funky_groups_anyhashable( elements, k,n,l,m ):     
    kn = lico( lico(elements,n),k)  # k groups of n elements
    lm = lico( lico( elements,m), l)  # l groups of m elements
    results =  [ list(flatten(r)) for r in product(kn, lm)]
    # added this line so that only each element was used once.. 
    return [ r for r in results if len(set( flatten( r))) == len(g) ]

In [103]: g = ["A1", "B2", 232, "D0", 32]

In [104]: get_funky_groups_anyhashable(g, 1,2,1,3)
Out[104]: 
[[('A1', 'B2'), (232, 'D0', 32)],
 [('A1', 232), ('B2', 'D0', 32)],
 [('A1', 'D0'), ('B2', 232, 32)],
 [('A1', 32), ('B2', 232, 'D0')],
 [('B2', 232), ('A1', 'D0', 32)],
 [('B2', 'D0'), ('A1', 232, 32)],
 [('B2', 32), ('A1', 232, 'D0')],
 [(232, 'D0'), ('A1', 'B2', 32)],
 [(232, 32), ('A1', 'B2', 'D0')],
 [('D0', 32), ('A1', 'B2', 232)]]

值得注意的是，如果性能成为问题。

In [132]: lico( combinations( g,2),1) == lico( lico( g,2),1 )
Out[132]: True

- dermen

---

抱歉如果不清楚，但这不是我要找的。例如，您的第一次迭代['AB'，'AC'，'ABC']：每个元素只能出现一次，因此您不能在任何组中跨越多个A，多个B，多个C。（我编辑了原帖;请参见规则＃1）。 - Bentley4

嗯，我认为你可以检查所提到的简单编辑中添加的扁平元素集。通过使用combinations工具，您已经比使用您链接到的permutations迭代工具少做了很多次迭代...但您可能还可以进一步优化... - dermen

Answer 3

这个问题并不像它一开始看起来那么简单：每个组必须是词典中的组合，而你需要所有互斥组合的排列。

我认为这将需要您编写一个递归生成器，使用字母表和大小列表。类似以下代码（恐怕我还没有测试...）：

def foo(lexicon, size_list, result):
    if len(size_list) == 0:
        yield result
        return
    size = size_list[0]
    for group in itertools.combinations(lexicon, size):
        # remove used items from the lexicon
        next_lex = lexicon[:]
        for item in group:
            next_lex.remove(item)
        # recur at next level
        foo(next_lex, size_list[1:], result + [group] )

foo( "ABCDEFG", [2, 2, 3], [] )

- Prune

---

返回一个空的生成器。 - Bentley4