algorithm - 无标记的排列组合。就像将几个元素尽可能均匀地分配到几个组中

Question

现在我有 7 个数字:1、2、3、4、5、6、7。我想把他们分成 3 组。喜欢 (1,2) (3,4) (5,6,7)但是，以下 4 个分配是相同的。

• (1,2) (3,4) (5,6,7)
• (3,4) (1,2) (5,6,7)
• (2,1) (4,3) (6,5,7)
• (7,5,6) (1,2) (4,3)

这个与上面4个作业不同。(1,3) (2,4) (5,6,7)

---

此外，每个组的元素数量必须尽可能接近。说 7=2+2+3，它不能像 7=1+3+3 或 7=1+2+4。我只以7个数3组为例，解法一定也适用于不同的数和组，比如9=2+2+2+3。

所以

---

1. 我的问题是什么类型的问题？
2. 如何找出每一个有效的分配？

Answer 1

它是一类分区的组合枚举。我的策略是将所有由两部分组成的分区循环到(大小为 q 的部分中的事物)和(大小为 q + 1 的部分中的事物)，然后在这些部分中进行所有偶数分区。

import itertools


def partition_by_index(lst, indexes):
  lsts = ([], [])
  indicator = [False] * len(lst)
  for i in indexes:
    indicator[i] = True
  for i, x in enumerate(lst):
    lsts[indicator[i]].append(x)
  return lsts


def enumerate_even_partitions(lst, k):
  n = len(lst)
  if n == 0:
    yield ((),) * k
    return
  q, r = divmod(n, k)
  assert r == 0
  for indexes in itertools.combinations(range(1, n), n - q):
    lst0, lst1 = partition_by_index(lst, indexes)
    for subpartition in enumerate_even_partitions(lst1, k - 1):
      yield (tuple(lst0),) + subpartition


def enumerate_maximally_even_partitions(lst, k):
  n = len(lst)
  q, r = divmod(n, k)
  # k - r parts of size q and r parts of size q + 1
  for indexes in itertools.combinations(range(n), r * (q + 1)):
    lst0, lst1 = partition_by_index(lst, indexes)
    for subpartition0 in enumerate_even_partitions(lst0, k - r):
      for subpartition1 in enumerate_even_partitions(lst1, r):
        yield subpartition0 + subpartition1