0

我需要一种算法来将集合S的所有分区精确地 生成为k < |S| 块。

注意：我已经找到了生成所有可能分区的算法；我只需要k 分区算法。

任何想法？

4

1 回答 1

1

在评论中，我建议在深度 k-1 处停止“通常的递归算法”，考虑到一个 2 级递归方案，其中每个外部递归步骤都是决定停止构建当前部分并开始构建下一个部分，并且每个内部递归步骤是决定将某些元素放入当前部分。这是一个相当不错的方案，因为这意味着各个 k 分区是在递归树的底部生成的，因此您可以根据需要立即对它们进行操作，而不必将它们全部存储到一个巨大的数组中供以后处理（当然，如果您愿意，您仍然可以这样做）。这里唯一的技巧是确保您不会以多种方式最终生成相同的分区 - 特别是通过生成包含相同部分的两个分区，但这些部分的顺序不同。这可以通过强制订购零件来避免。最简单的方法是在开始构建新部件时始终添加第一个（即最左边的）可用元素——这保证了分区中的部件将按其元素的最小位置排序。

但是，如果您不介意在内存中实例化完整的 k 分区列表，那么还有另一种我认为更简单的方法。以下内容应该足以帮助您组合一个简单的递归算法：

考虑 S 中的一些元素 s。S 的每个 k 分区恰好属于以下两个类别之一：

  1. s 与其他元素出现在同一部分。在这种情况下，从该部分中删除 s 会得到一个 S \ {s} 的 k 分区。
  2. s 单独出现在一部分中。在这种情况下，删除整个部分会给出 S \ {s} 的 (k-1)-分区。

情况 (1) 中的所有分区可以通过将 s 添加到 S \ {s} 的 k 分区中的一个部分来形成，并且情况 (2) 中的所有分区可以通过将仅包含 s 的单独部分添加到S \ {s} 的 (k-1)-分区。说服自己，这将仅一次生成 S 的所有 k 分区。

在递归期间，您需要考虑的唯一边界情况是当 |S| == k -- 在这种情况下，您需要返回由 k 个单例集组成的单个分区。

于 2014-03-02T13:07:42.367 回答