algorithm - 从子集列表中查找所有分区

Question

给定一个特定子集的列表，例如

S = [ {1, 2}, {3, 4}, {1}, {2, 3}, {4}, {3} ]

和一个“宇宙”集合

U = {1, 2, 3, 4}

有什么优雅而简单的算法可以用来从 S 中找到由集合组成的 U 的所有可能分区？在此示例中，此类分区包括

{1, 2} {3, 4}
{1, 2} {3} {4}

等等

Answer 1

使用递归。

根据是否使用第一个元素，将问题拆分为两个较小的问题：

• 分区使用{1,2}和任何剩余的集合。
• {1,2}不使用但使用任何剩余集合进行分区。

这两个选项涵盖了所有可能性。

• 第一个是通过{3,4}仅使用分区来解决的[ {3, 4}, {1}, {2, 3}, {4}, {3} ]。
• 第二个是通过{1,2,3,4}仅使用分区来解决的[ {3, 4}, {1}, {2, 3}, {4}, {3} ]。

要了解如何解决这些较小的问题，请参阅此类似问题。