查找列表中元素数量最少的所有无序分区

Question

给出了元素列表。我希望拥有将这个列表划分为任意数量的分区的所有可能性，以便每个分区至少有 x 个元素。列表中分区的顺序和分区中元素的顺序并不重要。 例如： List = [1,2,3,4] get_partitions(list,2) 应该返回：

[[1,2,3,4],
 [[1,2],[3,4]],
 [[1,3],[2,4]],
 [[1,4],[2,3]]]

List = [1,2,3,4] get_partitions(list,1) 应该返回：

[[1,2,3,4],
 [[1,2],[3,4]],
 [[1,3],[2,4]],
 [[1,4],[2,3]],
 [[1],[2],[3,4],
  ...]

我已经开始在Python中递归地实现这个，但我创造了太多多余的案例。出于运行时的原因，我想提前减少这些情况，而不是事后使用 freezesets 删除它们。

from itertools import combinations
import numpy as np
def get_partitions(liste,min,max=None):

    if max is None:
        # Default setting
        max = len(liste)
    if len(liste) == min :
        # Termination Criterium
        yield [liste]
    else:
        for r in range(np.min([len(liste),max]),min-1,-1):
            # max for avoiding cases like: [[1,2,3,4],[2,6]] and [[2,6],[1,2,3,4]]
            for perm in combinations(liste,r):
                rest = [i for i in liste if i not in perm]
                if len(rest) >= min:
                    for recurse in get_partitions(rest,min,r):
                        yield [list(perm)] + list(recurse)
                if len(rest) == 0:
                    # r == len(liste)
                    yield [list(perm)]

这导致：

[[[1, 2, 3, 4]],
 [[1, 2], [3, 4]],
 [[1, 3], [2, 4]], 
 [[1, 4], [2, 3]],
 [[2, 3], [1, 4]],
 [[2, 4], [1, 3]],
 [[3, 4], [1, 2]]]

提前感谢您的任何帮助。

---

尝试使用 @mozway 的答案并将其扩展为递归版本导致我：

def get_partitions(iterable, minl=2):
    s = set(iterable)

    for r in range(minl, len(s)//2+1):
        if len(s)//2 != r:
            for c in combinations(s, r):
                for recurse in get_partitions(list(s.difference(c)), minl):
                    yield [list(c),*recurse]
        else:
            for c in islice(combinations(s, r), comb(len(s),r)//2):
                for recurse in get_partitions(list(s.difference(c)), minl):
                    yield [list(c),*recurse]

    yield [list(s)]

对于示例 list = [1,2,3,4], x=1 ，它减少了 47 种可能性的数量（我最初的尝试) 到 19。不过，仍然存在大量多余的情况。

[[[1], [2], [3], [4]], <----
 [[1], [2], [3, 4]],
 [[1], [2, 3, 4]],
 [[2], [1], [3], [4]], <----
 [[2], [1], [3, 4]],
 [[2], [1, 3, 4]],
 [[3], [1], [2], [4]], <----
 [[3], [1], [2, 4]],
 [[3], [1, 2, 4]],
 [[4], [1], [2], [3]], <----
 [[4], [1], [2, 3]],
 [[4], [1, 2, 3]],
 [[1, 2], [3], [4]],
 [[1, 2], [3, 4]],
 [[1, 3], [2], [4]],
 [[1, 3], [2, 4]],
 [[1, 4], [2], [3]],
 [[1, 4], [2, 3]],
 [[1, 2, 3, 4]]]

Answer 1

这是一个很长的解决方案。在生成分区时不使用拒绝，因此从这个意义上说，这可能有点有效。尽管如此，还有很多东西需要优化。

示例：

list(get_partitions(range(3), 1))
# [[[0, 1, 2]], [[0], [1, 2]], [[1], [0, 2]], [[2], [0, 1]], [[0], [1], [2]]]

---

以下是其工作原理的概述：

• 首先，定义一个辅助 split 函数非常有用，该函数采用列表 lst 和整数 nn code> 并返回将列表分为两组的所有方法，一组的大小为 n ，另一组的大小为 len(lst) - n 。
• 其次，我们需要解决一个更简单的问题：如何将列表 lst 拆分为 n 个组，每个组的大小为 k。当然，这只有在len(lst) = n * k时才有可能。这是在 get_partitions_same_size 函数中实现的。这个想法是始终将 lst 的第一个元素包含在第一组中并递归。
• 第三，我们需要找到 len(lst) 的所有整数分区。我从这个线程复制了代码。
• 第四，对于len(lst)的每个整数分区p，我们需要找到所有对lst进行分区的方法根据 p。
  • 例如，len(lst) == 7 和 p = 3 + 2 + 2。在这种情况下，我们可以为第一组选择任意三个元素，为第二组选择任何剩余的两个元素，而对于最后的第三组则无需进行选择。
  • 这可能会引入冗余，因为我们可以获得仅最后两组的顺序不同的两个分区。
  • 为了解决这个问题，我们可以通过计算每个大小的组的数量来表示一个分区。在此示例中，p 对应于 p_scheme = [(3, 1), (2, 2)]。函数get_partitions_helper接收一个列表lst和一个“分区方案”p_scheme，并返回所有相应的分区，而不进行重复计数。这是使用第二步中的 get_partitions_same_size 的地方。

• 最后，所有内容都集中在 get_partitions 中：我们循环遍历 len(lst) 的整数分区，并返回与每个可能的整数分区相对应的所有可能的列表分区。

这是一个有趣的问题，非常欢迎对错误和优化提出评论。

---

from itertools import combinations
from collections import Counter

# from this thread:
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning
def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p


def split(lst, n):
  '''
  return all ways to split lst into two groups, 
  with n and len(lst) - n elements respectively
  '''
  assert len(lst) >= n
  # handle special case of len(lst) == 2 * n
  if len(lst) == 2 * n:
    for first, second in split(lst[1:], n-1):
      yield [lst[0], *first], second
  else:
    for comb in combinations(range(len(lst)), n):
      comb = set(comb)
      first = [x for i, x in enumerate(lst) if i in comb]
      second = [x for i, x in enumerate(lst) if i not in comb]
      yield first, second


def get_partitions_same_size(lst, n, k):
  # print(lst, n, k)
  'return all ways to partition lst into n parts each of size k up to order'
  if len(lst) != n * k:
    print(lst, n, k)
  assert len(lst) == n * k
  if n == 0 and len(lst) == 0:
    yield []
  # case when group size is one
  elif k == 1:
    yield [[x] for x in lst]
  # otherwise, without loss, the first element of lst goes into the first group
  else:
    for first, rest in split(lst[1:], k-1):
      for rec_call in get_partitions_same_size(rest, n-1, k):
        yield [[lst[0], *first], *rec_call]


def get_partitions_helper(lst, p_scheme):
  """
  return all ways to partition lst into groups according to a partition scheme p_scheme

  p_scheme describes an integer partition of len(lst)
  for example, if len(lst) == 5, then possible integer partitions are:
  [(5,), (1, 4), (1, 1, 3), (1, 1, 1, 2), (1, 1, 1, 1, 1), (1, 2, 2), (2, 3)]
  for each, we count the number of groups of a given size
  the corresponding partition schemes are:
  [[(5, 1)],
  [(1, 1), (4, 1)],
  [(1, 2), (3, 1)],
  [(1, 3), (2, 1)],
  [(1, 5)],
  [(1, 1), (2, 2)],
  [(2, 1), (3, 1)]]
  """
  if not lst and not p_scheme:
    yield []
    return 
  assert len(lst) == sum(a * b for a, b in p_scheme)
  group_size, group_count = p_scheme[0]
  num_elts = group_size * group_count
  for first, second in split(lst, num_elts):
    for firsts in get_partitions_same_size(first, group_count, group_size):
      for seconds in get_partitions_helper(second, p_scheme[1:]):
        yield [*firsts, *seconds]


def get_partitions(lst, min_):
  """
  get all partitions of lst into groups s.t. each group has at least min_ elements
  up to order (of groups and elements within a group)
  """
  for partition in partitions(len(lst), min_):
    p_scheme = list(Counter(partition).items())
    yield from get_partitions_helper(lst, p_scheme)

Answer 2

这看起来像是带有补集的部分幂集。

您不需要定义最大值，一旦设置了最小值，它就固定了。

另外，包括完整集是一种特殊情况（从技术上讲，完整集是集合+空集，因此它违反了最小条件）

要限制组合的数量，只要拥有总长度的前一半即可。如果您有偶数输入并选择半分区，则仅计算一半的组合（使用itertools.islice）：

您可以使用：

from itertools import combinations
from math import comb

def get_partitions(iterable, minl=2):
    s = set(iterable)
    return [list(s)]+\
           [[list(c), list(s.difference(c))]
            for r in range(minl, len(s)//2+1)
            for c in ( combinations(s, r) if len(s)//2 != r else
             islice(combinations(s, r), comb(len(s),r)//2))
           ]

out = get_partitions([1,2,3,4])

输出：

[[1, 2, 3, 4],
 [[1, 2], [3, 4]],
 [[1, 3], [2, 4]],
 [[1, 4], [2, 3]]]

其他示例：

>>> get_partitions([1,2,3,4,5,6], 1)

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