2

我正在尝试获取点集并将它们分成较小的集。约束是每个集合的每个维度都有一些最小值和一些最大值。我想生成这些集合的所有可能组合（我们称之为一组集合。）当我完成后，每个点都出现在每个集合中的一个集合中。

例如，假设我只有具有两个自变量 i 和 j 的数据点。他们是：

(1,1) (1,2) (2,2) (3,1),(2,1),(2,3)

这些分裂中的任何一个都很好：

(1,1)(1,2) and (2,2)(3,2)(2,1)(2,3)
First set has i < 2, second set has i >= 2.

(1,1)(3,1)(2,1) and (1,2)(2,2)(2,3)
First set has j < 2, second set has j >= 2.

(1,1)(1,2) and (2,2)(3,1)(2,1) and empty and (2,3)
First set has (i < 2, j < 3), second set has (i >= 2, j < 3)
Third set has (i < 2, j >= 3), fourth set has (i >= 2, j >= 3)

如何在不手动迭代每个点（不同的数字）的情况下生成整组拆分！次？

这不是家庭作业，只是我试图作为数据拟合器的一部分编写的程序。

4

1 回答 1

1

假设意图是在每个维度中最多有一个分割点（因此相对于该维度将点划分为最多两组），那么：

对于每个维度，让 V 是该维度中的坐标集。例如，给定点 (4, 10), (4, 20), (6, 10), (6, 18), (7, 3)，那么对于第一个维度，V 是 {4, 6, 7 }。通过集合中的每个值迭代 v。

嵌套这些迭代，每个维度一个，这样，在最内层循环的主体中，每个维度都有 av 。我们将它们编号为 v0、v1、v2、...

每个 v 形成一个标准：x < v 或 v <= x。对于 n 个维度，这些标准有 2 n种组合。每个组合指定原始点的一个子集。例如，一个这样的子集是 { p | x0 < v0 and v1 <= x1 and v2 <= x2 and... }，其中点 p 的坐标为 (x0, x1, x2,...)。因此，遍历 2 n 个潜在子集（有些相同，因为它们是空的），并将它们收集到一个集合中。那是原始点集的一个分区。

当您完成通过它们的值迭代 v 时，您将构建符合您的条件的每个分区。

于 2012-08-05T17:36:26.420 回答