python中K项的L组中N个元素的组合

Question

给定N个元素的列表，例如

mylist = [0, 1, 2, 3, 4, 5, 6, 7]

我想找到L组中K元素的所有组合，例如K=4，L=2， 结果将是

          L=0            L=1 
 1)   [0, 1, 2, 3]   [4, 5, 6, 7]
 2)   [0, 1, 2, 4]   [3, 5, 6, 7]
 3)   [0, 1, 2, 5]   [3, 4, 6, 7]

              ... etc...
69)   [4, 5, 6, 7]   [0, 1, 2, 3]

注意[0, 1, 2, 3]和[0, 1, 3, 2]将被计算为第一组的相同组合

对于案例L=2，我使用以下方法

from itertools import combinations

N = 8
M = 4
L = N // M

combs = list(combinations(range(N), M))
allidx = list(range(N))

for c, comb in enumerate(combs):

    idx1 = list(comb)
    idx2 = list(set(allidx) - set(idx1))

    print(c, idx1,'\t',idx2)

首先，这种“组合”的数学定义是什么

第二，在L>2的情况下，有没有比计算所有置换并在之后修剪它们更有效的方法来计算它们

Answer 1

下面是一种从长度n的集合生成大小为k的所有唯一分区的方法

此类分区的数量为（p为部件数量，等于L）：

NPK(n,k) = n! / ((k!)^p * p!)

生长迅速（n=9时为280，k=3）

算法递归地将项分布在各个部分上。为了避免重复生成相同的分区（如01 23 45和01 45 23），我们应该限制每个组的前导（最小）元素的位置

这里我使用了lastfilled参数作为最右边填充部分的索引，因此项目0始终属于第0部分，项目1可能属于第0部分或第1部分，但不属于第2部分，依此类推。有了中间结果01 __ __，我们只能在下一个级别生成01 2_ __，而不是01 __ 2_

def genp(l, parts, cnts, n, k, p,  m, lastfilled):
    if m == n:
        l.append(parts[:])
        return
    for i in range(min(p, lastfilled + 2)):
        if cnts[i] < k:
            parts[i][cnts[i]] = m
            cnts[i] += 1
            genp(l, parts, cnts, n, k, p, m+1, max(i, lastfilled))
            cnts[i] -= 1


def genpartssizek(n, k):
    l = []
    p = n // k
    parts = [[0]*k for _ in range(p)]
    cnts = [0]*p
    genp(l, parts, cnts, n, k, p,  0, -1)
    return l

print(genpartssizek(6,2))

[[[0, 1], [2, 3], [4, 5]], 
 [[0, 1], [2, 4], [3, 5]], 
 [[0, 1], [2, 5], [3, 4]],
 [[0, 2], [1, 3], [4, 5]], 
 [[0, 2], [1, 4], [3, 5]], 
 [[0, 2], [1, 5], [3, 4]], 
 [[0, 3], [1, 2], [4, 5]], 
 [[0, 4], [1, 2], [3, 5]], 
 [[0, 5], [1, 2], [3, 4]], 
 [[0, 3], [1, 4], [2, 5]], 
 [[0, 3], [1, 5], [2, 4]], 
 [[0, 4], [1, 3], [2, 5]], 
 [[0, 5], [1, 3], [2, 4]], 
 [[0, 4], [1, 5], [2, 3]], 
 [[0, 5], [1, 4], [2, 3]]]

Answer 2

您可以使用递归函数，从列表中获取k元素的所有组合，并将它们与其余元素的组合组合

import itertools

def combs(lst, k, l):
    if l == 0:
        yield []
    else:
        for c in itertools.combinations(lst, k):
            rest = [x for x in lst if x not in c]
            for res in combs(rest, k, l-1):
                yield [c, *res]

mylist = [0, 1, 2, 3, 4, 5, 6, 7]
for res in combs(mylist, 4, 2):
    print(res)

这里，只有当列表中的元素是唯一的时，部分rest = [x for x in lst if x not in c]才会起作用。如果可能存在重复的元素，您可以只获取索引的组合，例如，如下所示（其余部分保持不变）：

        for idc in itertools.combinations(range(len(lst)), k):
            comb = [lst[i] for i in idc]
            idc_set = set(idc)
            rest = [x for i, x in enumerate(lst) if i not in idc_set]
            for res in combs(rest, k, l-1):
                yield [comb, *res]

（同样，这假设lst至少有l*k个元素。）