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

Question

在 Python 中；获取 k 组 n 成员和 l 组 m 组合列表的最佳方法是什么给定可能成员列表的成员 g?

示例，给定一个元素列表:

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. 我不希望任何组中的元素重复(相当于说:我希望每个不同的元素在所有组中针对每个不同的组合出现一次)。

   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 中，我不希望在 k-groups 中出现相同的组合，如果 l-groups 是相同的(对于 l-groups 也是相同的)。

   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并在每个排列中将 k 组 n 和 l 组 m 组合在一起，但我会有对更多元素进行大量不必要的迭代。

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'),
 ...,
]

详细信息和见解可以在 demonstration 中找到.