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

Question

在Python中；获得n成员的k组和{}成员的{}组的组合列表的最佳方法是什么？

例如，给定元素列表：

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

我想要的是有一个所有组合的列表li，例如2（=k）组（=n）和1（=l）组的3（=m）：

^{pr2}$

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

   E.g. ["AB", "AD", "EFG"] is not a valid combination as it has the element A more than once accross all groups.

2. 我不想在一个组内有不同的排列

   E.g. ["AB", "CD", "EFG"] should not be repeated in a form like ["BA", "DC", "EGF"].

3. 另外，如果一个组合出现在k-groups中的任何一个中，如果{}只是相同的（l-groups）我不希望在k-群中出现相同的组合。在

   E.g. if["AB", "CD", "EFG"] appears, [ "CD", "AB", "EFG"] should not appear again.

为了清楚起见，我只对这些组总是整齐地/完全地适合要使用的元素的总组（g）的情况感兴趣：

E.g. 2x2 + 1x3 == 7 == len(["A", "B", "C", "D", "E", "F", "G"]), 1x2 + 1x3 == 5 == len(["A", "B", "C", "D", "E"]).

---

我可以使用Python's permutations function并在每个排列中组合成n的k组和{}的{}组，但是对于更多元素，我将有很多不必要的迭代。在

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

输出：

^{pr2}$

细节和细节可以在demonstration中找到。在

Answer 2

这个问题并不像它第一次出现的那样简单：从词汇表上看，每个组都必须是一个组合，并且您需要这些组的所有互斥排列。在

我认为这需要你编写一个递归生成器，使用字母表和大小列表。类似下面的代码（恐怕我还没有测试过…）公司名称：

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

Answer 3

编辑：在澄清之后，我添加了一行应该完成解决方案…

这个怎么样，它使用了几个itertools和{a2}。无论如何，我想itertools.组合是您要使用的：

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结果

^{pr2}$

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

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