将单组行和列分解为 n 个随机行和随机列的矩形片段的算法，随机重叠

Question

我想将(给定的)单组 D 行和列(例如电子表格或数据库表)数据转换为随机生成的 N 个片段集，给定数字 n <= N，其中片段还包含随机重叠的数据。 n = N 是更可取的，但不是必需的。D 中的每个数据点(单元格)必须包含在至少一个片段中。

澄清一下:“n”是用户提供的一个非零整数，意思是“使用 D，至少还给我 n 个片段”。 “N”是返回的实际片段数。可接受的算法是生成至少 n 个片段。对于两个可接受的算法 X 和 Y，如果 X 产生的 N 比 Y 产生的 N 更接近 n，则 X 是比 Y 更好的解决方案。

此外，任何片段中任何一行中的数据也必须包含在 D 中的一行中。(每个片段还需要包含一个标识符列，例如行 ID 或其他具有唯一值的列，但这应该在片段输出时添加是微不足道的)。因此，例如，如果 D 包含姓名和电话号码以及其他列，那么任何包含姓名和电话号码的片段都应该始终具有与该行的姓名相关联的正确电话号码。

一般来说，如果任何列存在于片段中的任何位置，则该片段的每一行都必须存在(例如，如果第 1 行包含列 A、B 和 C，则第 2 行必须包含这些相同的列)，列也是如此(例如，如果 B 列包含第 4、5 和 6 行，则片段中的每个其他列也必须包含第 4、5 和 6 行)。

如果 N = 4，那么我想到的最简单的方法是:

1. 为每一行掷一枚硬币。如果是头，则分配给片段 1
2. 为每一行掷一枚硬币。如果是头，则分配给片段 2
3. 对于每一行，如果它既没有分配给片段 1 也没有分配给片段 2，则掷硬币，如果正面朝上，则分配给片段 1，否则分配给片段 2
4. 对所有列重复上述 3 个步骤。现在我们有碎片 1 和 2，但这些不一定涵盖 D 中的所有数据。接下来是 3 和 4。
5. 为每一行掷一枚硬币。如果是头，则分配给片段 3；否则，如果此行已分配给片段 2，但未分配给片段 1，则分配给片段 3。
6. 对于每一列，掷一枚硬币。如果是头，则分配给片段 3；否则，如果此列已分配给片段 2 但未分配给片段 1，则分配给片段 3。
7. 为每一行掷一枚硬币。如果是头，则分配给片段 4；否则，如果此行已分配给片段 1，但未分配给片段 2，则分配给片段 4。
8. 对于每一列，掷一枚硬币。如果是头，则分配给片段 4；否则，如果此列分配给片段 1 但未分配给片段 2，则分配给片段 4

我相信这应该会产生 4 个看起来像这样的片段，假设行和列被重新排序为片段 1 的连续 block ，并且在不与片段 1 冲突的情况下尽可能地与片段连续2(绿色是黄色+蓝色重叠的地方):

但是，这种方法似乎难以扩展到更高的 N 值。是否有更简单的方法将其推广到任何 n 或 N 值？

Answer 1

--编辑(添加第0步)--

第 0 步。随机分配每个片段的概率权重；随机挑选时使用这些权重。您可能需要分别为步骤 1 和步骤 2 使用不同的权重结构。

第 1 步。为每列分配一组随机片段(这在某种程度上类似于@Jim 为每个单元格提出的建议，但基于列)。所以最后，每一列都属于一个或多个片段。如果每列至少分配 2 个片段会更好；我在下面解释为什么我建议这个技巧。

您应该要求进行最终检查以确保所有片段至少出现一次，如果没有出现，请尝试将缺失的片段添加到随机列数中。

在这个阶段所有片段都存在，但它们占据了每一行。

第 2 步。扫描每一行并随机删除该行的一些(不是全部)分配片段。您不能删除仅从该片段表示该行上至少一个单元格的片段。这就是为什么在第 1 步中，我建议您每列至少选择 2 个片段，这样您始终可以安全地删除每行至少一个片段。如果您不这样做，一些片段(那些是至少一列中唯一占用的片段)可能永远不会被删除，并且会继续占据每一行。

执行最后一次检查以确保您没有完全删除任何碎片。

注意 1。您可以通过以下概率以某种方式控制重叠密度:a) 在步骤 1 中每列选择 X 个片段，b) 在步骤 2 中每行删除 Y 个片段。

注意 2. 步骤 1 可以针对行运行，步骤 2 可以针对列运行，也许最好将步骤 1 应用于更大的维度(以符合 OP 注释)。