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

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.

所以

我的问题是什么问题？
如何找出每一个有效的分配？

Answer 1

它是 class 分区的组合枚举。我的策略是将所有两部分分区循环到（大小为 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

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

Unmarked permutation and combination. Like assigning several elements into several groups as evenly as possible

algorithm

combinations