（有序）在固定大小的块中设置分区

Question

这是我想写的一个函数，但无法这样做。即使你 不/不能给出解决方案，如果有提示，我将不胜感激。例如， 我知道有序表示之间存在相关性 整数和有序集分区的总和，但仅此一点并不能帮助我 找到解决方案。所以这里是我需要的函数的描述：

任务

创建一个高效的*函数

List<int[]> createOrderedPartitions(int n_1, int n_2,..., int n_k)

，返回集合的所有集合部分的数组列表 {0,...,n_1+n_2+...+n_k-1} 位于 参数数量 大小的块中（在此 顺序）n_1,n_2,...,n_k（例如n_1=2, n_2=1, n_3=1 -> ({0,1},{3},{2 }),...)。

这是一个用法示例：

int[] partition = createOrderedPartitions(2,1,1).get(0);
partition[0]; // -> 0
partition[1]; // -> 1
partition[2]; // -> 3
partition[3]; // -> 2

请注意，列表中的元素数量是 (n_1+n_2+...+n_n 选择 n_1) * (n_2+n_3+...+n_n 选择 n_2) * ... * （n_k 选择 n_k）。此外，createOrderedPartitions(1,1,1) 将创建 {0,1,2} 的排列，因此会有 3! = 6 元素 列表。

* 通过高效我的意思是你不应该最初创建一个更大的列表 像所有分区一样，然后过滤掉结果。你应该直接这样做。

额外要求

如果参数为 0，则将其视为不存在，例如 createOrderedPartitions(2,0,1,1) 应该产生与以下相同的结果 createOrderedPartitions(2,1,1)。但至少有一个参数不能为 0。 当然，所有参数必须 >= 0。

备注

提供的伪代码是准 Java，但解决方案的语言 没关系。事实上，只要解决方案相当通用并且可以 能用其他语言复制是理想的。

实际上，更好的是 List> 返回类型（例如，当 在 Python 中创建这样的函数）。然而，随后的论点有 不得忽略 0 值。 createOrderedPartitions(2,0,2) 然后 创建

[({0,1},{},{2,3}),({0,2},{},{1,3}),({0,3},{},{1,2}),({1,2},{},{0,3}),...]

背景

我需要这个功能来使我的 mastermind-variation 机器人更加高效和 最重要的是代码更“漂亮”。看一下 filterCandidates 我的源代码中的函数。有不必要的 / 重复查询，因为我只是使用排列而不是 特别订购的分区。另外，我只是对如何写感兴趣 这个功能。

我对（丑陋的）“解决方案”的想法

创建 {0,...,n_1+...+n_k} 的幂集，过滤掉 size 的子集 n_1, n_2 等并创建 n 个子集的笛卡尔积。然而 这实际上行不通，因为会有重复项，例如 ({1,2},{1})...

首先选择 x = {0,...,n_1+n_2+... 中的 n_1 +n_n-1} 并将它们放入 第一组。然后选择 x 中的 n_2，不包含 n_1 个所选元素 事先等等。然后您会得到例如 ({0,2},{},{1,3},{4})。的 当然，必须创建每种可能的组合，因此 ({0,4},{},{1,3},{2}), 也是如此，等等。似乎很难实施，但也许是可能的。

研究

我猜这个 朝着我想要的方向发展，但我不知道如何将它用于我的 具体场景。

http://rosettacode.org/wiki/Combinations

Answer 1

您知道，表达您的想法通常有助于找到解决方案。似乎潜意识就开始处理任务，并在找到解决方案时通知你。所以这是我在 Python 中的问题的解决方案：

from itertools import combinations

def partitions(*args):
    def helper(s, *args):
        if not args: return [[]]
        res = []
        for c in combinations(s, args[0]):
            s0 = [x for x in s if x not in c]
            for r in helper(s0, *args[1:]):
                res.append([c] + r)
        return res
    s = range(sum(args))
    return helper(s, *args)

print partitions(2, 0, 2)

输出是：

[[(0, 1), (), (2, 3)], [(0, 2), (), (1, 3)], [(0, 3), (), (1, 2)], [(1, 2), (), (0, 3)], [(1, 3), (), (0, 2)], [(2, 3), (), (0, 1)]]

它足以将算法翻译为 Lua/Java。这基本上是我的第二个想法。

算法

正如我在问题中已经提到的，基本思想如下：

首先选择集合 s := {0,...,n_1+n_2+...+ 的 n_1 个元素n_n-1} 并将它们放入
结果列表中第一个元组的第一组（例如，如果所选元素为 0,1,2，则 [({0,1,2},...)然后选择集合 s_0 := s 中的 n_2 个元素，而无需事先选择 n_1 个元素，这样的元组可能是 ({0,2。 },{},{1,3},{4})。
当然，每种可能的组合都会被创建，因此 ({0,4},{},{1,3},{2}) 是另一个这样的元组，依此类推。

实现

首先创建要使用的集合（s = range(sum(args))）。然后这个集合和参数被传递给递归辅助函数helper。

helper 执行以下操作之一： 如果处理了所有参数，则返回“某种空值”以停止递归。否则，迭代传递的长度 args[0] 的集合 s 的所有组合（helper 中 s 之后的第一个参数）。在每次迭代中创建不包含 c 中的元素的集合 s0 := s（c 中的元素是从 s 中选择的元素），其中然后用于 helper 的递归调用。

那么 helper 中的参数会被一一处理。 helper 可能首先以 helper([0,1,2,3], 2, 1, 1) 开头，在下一次调用中它是 helper ([2,3], 1, 1)，然后是 helper([3], 1)，最后是 helper([])。当然，另一个“树路径”是 helper([0,1,2,3], 2, 1, 1), helper([1,2], 1, 1 ) 、 helper([2], 1)、helper([])。创建所有这些“树路径”，从而生成所需的解决方案。