迭代器遍历所有分成k组的分区？

Question

假设我有一个列表L。如何获得一个遍历K组所有分区的迭代器？

例如：L = [ 2,3,5,7,11, 13]，K = 3

所有3组分区的列表：

[ [ 2 ], [ 3, 5], [ 7,11,13] ]
[ [ 2,3,5 ], [ 7, 11], [ 13] ]
[ [ 3, 11 ], [ 5, 7], [ 2, 13] ]
[ [ 3 ], [ 11 ], [ 5, 7, 2, 13] ]
etc...

=== 更新 ===

我正在解决一个问题，看起来已经有效了，所以我将只是复制粘贴它。

# -*- coding: utf-8 -*-

import itertools 

# return ( list1 - list0 )
def l1_sub_l0( l1, l0 ) :
    """Substract two lists"""
    #
    copy_l1 = list( l1 )
    copy_l0 = list( l0 )

    #
    for xx in l0 :
        #
        if copy_l1.count( xx ) > 0 :
            #
            copy_l1.remove( xx )
            copy_l0.remove( xx )

    #
    return [ copy_l1, copy_l0 ]


#
def gen_group_len( n, k ) :
    """Generate all possible group sizes"""

    # avoid doubles
    stop_list = []
    #
    for t in itertools.combinations_with_replacement( xrange( 1, n - 1 ), k - 1 ) :
        #
        last_n = n - sum( t )

        # valid group size
        if last_n  >= 1 :
            res = tuple( sorted( t + ( last_n, ) ) )
            #
            if res not in stop_list :
                yield res
                stop_list.append( res )


# group_len = (1, 1, 3)

def gen( group_len, my_list ) :
    """Generate all possible partitions of all possible group sizes"""

    #
    if len( group_len ) == 1 :
        yield ( tuple( my_list ), )

    #
    else :

        # need for a stop list if 2 groups of same size
        stop_list = []

        #
        for t in itertools.combinations( my_list, group_len[ 0 ] ) :
            #
            reduced_list = l1_sub_l0( my_list, t )[ 0 ]

            #
            for t2 in gen( group_len[ 1: ], reduced_list ) :
                #
                tmp = set( ( t, t2[ 0 ] ) )
                #
                if tmp not in stop_list :
                    yield ( t, ) + t2
                    # avoid doing same thing twice
                    if group_len[ 1 ] == group_len[ 0 ] :
                        stop_list.append( tmp )


#
my_list = [ 3,5,7,11,13 ]
n = len( my_list )
k = 3

#
group_len_list = list( gen_group_len( n, k ) )
print "for %i elements, %i configurations of group sizes" % ( n, len(  group_len_list ) )
print group_len_list

#
for group_len in group_len_list :
    #
    print "group sizes", group_len
    #
    for x in gen( group_len, my_list ) :
        print x
    #
    print "==="

输出：

for 5 elements, 2 configurations of group sizes
[(1, 1, 3), (1, 2, 2)]
group sizes (1, 1, 3)
((3,), (5,), (7, 11, 13))
((3,), (7,), (5, 11, 13))
((3,), (11,), (5, 7, 13))
((3,), (13,), (5, 7, 11))
((5,), (7,), (3, 11, 13))
((5,), (11,), (3, 7, 13))
((5,), (13,), (3, 7, 11))
((7,), (11,), (3, 5, 13))
((7,), (13,), (3, 5, 11))
((11,), (13,), (3, 5, 7))
===
group sizes (1, 2, 2)
((3,), (5, 7), (11, 13))
((3,), (5, 11), (7, 13))
((3,), (5, 13), (7, 11))
((5,), (3, 7), (11, 13))
((5,), (3, 11), (7, 13))
((5,), (3, 13), (7, 11))
((7,), (3, 5), (11, 13))
((7,), (3, 11), (5, 13))
((7,), (3, 13), (5, 11))
((11,), (3, 5), (7, 13))
((11,), (3, 7), (5, 13))
((11,), (3, 13), (5, 7))
((13,), (3, 5), (7, 11))
((13,), (3, 7), (5, 11))
((13,), (3, 11), (5, 7))
===

- usual me

---

你目前尝试了什么？ - Paolo Casciello

参见：查找所有k子集分区 - Martin Thoma

请注意，查找所有k子集分区中描述的算法返回所有_非空_子集。由于OP没有提到这是一个限制条件，我认为该算法不适合他的目的。 - Kurt Peek

你认为 ((3,), (5,), (7, 11, 13)) 和 ((7, 11, 13)), (3,), (5,)) 是相同的吗？ - pylang

Answer 1

使用more_itertools.partitions（注意末尾的“s”）过滤大小为k的分区： 给定：

import itertools as it

import more_itertools as mit


iterable = [2, 3, 5, 7, 11]
k = 3

演示

res = [p for perm in it.permutations(iterable) for p in mit.partitions(perm) if len(p) == k]
len(res)
# 720

res
# [[[2], [3], [5, 7, 11]],
#  [[2], [3, 5], [7, 11]],
#  [[2], [3, 5, 7], [11]],
#  [[2, 3], [5], [7, 11]],
#  [[2, 3], [5, 7], [11]],
#  [[2, 3, 5], [7], [11]],
#  ...
#  [[3], [2], [5, 7, 11]],
#  [[3], [2, 5], [7, 11]],
#  [[3], [2, 5, 7], [11]],
#  [[3, 2], [5], [7, 11]],
#  [[3, 2], [5, 7], [11]],
#  [[3, 2, 5], [7], [11]],
#  [[3], [2], [5, 11, 7]],
#  ...
# ]

这个版本提供了一个排列输入的分区。可以包括重复元素的分区，例如[[3,], [5,], [7, 11, 13]]和[[7, 11, 13]，[3,]，[5,]]。

注意: more_itertools是第三方软件包。通过> pip install more_itertools进行安装。

- pylang

---

如果我正确理解了OP的问题，那么这是对另一个问题的很好回答，但它对于这个问题给出了错误答案，因为它约束子集必须相对于原始顺序连续。（例如，您的列表不包括任何包含子集[3,11]的分区，因为3和11在原始列表中不相邻）。 - teichert

这是一个很好的观察。是的，partitions 的这个版本返回连续元素的分区。我们可以使用 itertools.permutations 来解决这个问题。请参见更新。 - pylang

Answer 2

这样做可以实现目标，但可能效率很低（我对它们进行排序以避免重复计数）。

def clusters(l, K):
    if l:
        prev = None
        for t in clusters(l[1:], K):
            tup = sorted(t)
            if tup != prev:
                prev = tup
                for i in xrange(K):
                    yield tup[:i] + [[l[0]] + tup[i],] + tup[i+1:]
    else:
        yield [[] for _ in xrange(K)]

它也返回空簇，因此您可能希望在外部包装以仅获取非空簇：

def neclusters(l, K):
    for c in clusters(l, K):
        if all(x for x in c): yield c

仅为了检查而计数：

def kamongn(n, k):
    res = 1
    for x in xrange(n-k, n):
        res *= x + 1
    for x in xrange(k):
        res /= x + 1
    return res

def Stirling(n, k):
    res = 0
    for j in xrange(k + 1):
        res += (-1)**(k-j) * kamongn(k, j) * j ** n
    for x in xrange(k):
        res /= x + 1
    return res

>>> sum(1 for _ in neclusters([2,3,5,7,11,13], K=3)) == Stirling(len([2,3,5,7,11,13]), k=3)
True

它起作用了！

输出结果：

>>> clust = neclusters([2,3,5,7,11,13], K=3)
>>> [clust.next() for _ in xrange(5)]
[[[2, 3, 5, 7], [11], [13]], [[3, 5, 7], [2, 11], [13]], [[3, 5, 7], [11], [2, 13]], [[2, 3, 11], [5, 7], [13]], [[3, 11], [2, 5, 7], [13]]]

- val

---

很高兴能够帮忙！我认为如果你的列表已经排序，你可能可以绕过整个“sorted”/“if tup != prev”部分，并仅生成必要的部分。但这留给读者自己练习 :) - val

Answer 3

这个问题的一个简单替代方法是将三个聚类标签之一分配给每个元素。

import itertools
def neclusters(l, k):
    for labels in itertools.product(range(k), repeat=len(l)):
        partition = [[] for i in range(k)]
        for i, label in enumerate(labels):
            partition[label].append(l[i])
        yield partition

与@val的回答一样，可以将其包装起来以删除具有空聚类的分区。

- joeln

---

这个解决方案包括重复的分区，但是如果你过滤掉空的分区，对每个分区进行排序，然后去除重复项，你将得到所有给定子集数量的分区：例如 n=5; set(map((lambda p: tuple(sorted(map(tuple, filter(len, p))))), neclusters(range(n), n)))（在这种情况下有52个不同的分区）。 - teichert

Answer 4

编辑: 正如@moose所指出的，以下仅确定连续索引在同一群集中的分区。在所有排列上执行此分区将给出所寻找的答案。

Itertools对于这种组合列表非常有用。首先，我们将您的任务视为在数组中选择所有k-1个不同分割点的等效问题。这通过itertools.combinations解决，它返回给定可迭代对象的特定大小的无替换组合，并且返回的值按其在原始可迭代对象中找到的顺序排序。

因此，您的问题可以通过以下方式解决：

import itertools
def neclusters(l, K):
    for splits in itertools.combinations(range(len(l) - 1), K - 1):
        # splits need to be offset by 1, and padded
        splits = [0] + [s + 1 for s in splits] + [None]
        yield [l[s:e] for s, e in zip(splits, splits[1:])]

numpy的split函数旨在根据分割偏移量进行分区，因此这里提供了一种生成numpy数组列表的替代方法：

import itertools
def neclusters(l, K):
    for splits in itertools.combinations(range(len(l) - 1), K - 1):
        yield np.split(l, 1 + np.array(splits))

- joeln

---

这似乎是错误的。它只能找到不改变元素顺序的分区。但对于 l=[0,1,2] 和 K=2，它无法找到 [[0,2],[1]]。 - Martin Thoma

实际上，他的答案是唯一正确的。问题要求列出分区列表，而不是集合分区。 - Rok Kralj

看起来OP给出的例子是集合划分（尽管输入是列表）。（例如 [3, 11]，[5, 7]，[2, 13]） - teichert

Answer 5

一种相对高效的方法是在每次递归中以第一个元素为基准进行旋转，以强制唯一性，并且仅遍历所有递增大小的组合，直到达到会产生空子集的点。

def kpartitions(l, k):
  import itertools
  if k == 1: yield [l]; return
  for i in range(1, len(l)-k+1+1):
    s = set(range(1, len(l)))
    for comb in itertools.combinations(s, i-1):
      for t in kpartitions([l[idx] for idx in s - set(comb)], k-1):
        yield [[l[0], *(l[idx] for idx in comb)], *t]
def stirlingsecond(n, k):
  import math
  return sum((-1 if (i & 1 != 0) else 1) * math.comb(k, i)*((k-i)**n)
    for i in range(k+1)) // math.factorial(k)
assert len(list(kpartitions([3,5,7,11,13], 3))) == stirlingsecond(5, 3)
assert len(list(kpartitions([2,3,5,7,11,13], 3))) == stirlingsecond(6, 3)

这种方法非常高效，尽管它会多做一些工作来查找不在组合中的元素，因为itertools.combinations很方便，但编写一个同时生成组合和不在其中的元素的组合函数可能会带来恒定时间的改进。

- Gregory Morse