一组集合的所有可能子集的集合算法

Question

3

我很难想出一个算法来生成一组集合的所有可能子集。也就是说，给定一个集合S，我想知道包含S中子集的所有可能集合。我可能没有描述清楚，所以我将举个例子来说明。

如果S = {1, 2, 3}，

我要找的是：

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

虽然繁琐，但我可以手动生成这些内容，但我很难想出一个算法用于编码实现。

- user4238474

3

请尝试搜索“集合分割”，这就是您在此寻找的内容。 - Vincent van der Weele

1

请问您尝试过什么方法，还是只想让 Stack Overflow 帮您解决这个问题？ - SMA

这种情况似乎适合使用动态规划算法来解决。 - Zeks

DP 可以有效地帮助计算分区的数量，但如果目标是生成它们，那么这听起来像是一个递归问题。 - sbeliakov

我最初花了一些时间用笔和纸，手写着集合。我想到的第一个实现方法是递归，但出于某种原因，解决方案没有浮现在我的脑海中。我看到下面的建议，并验证它确实解决了问题。我唯一能想到的为什么我自己没有解决它的原因是“脑抽”。 - user4238474

3个回答

0

你可以使用递归算法，就像下面的帖子一样，概念是相同的。我之前已经回答过这个问题了。

- Sridhar DD

0

我在这里看到两个独立的任务：

然后你需要对每个排列应用每个分区。这将产生所有可能的结果集Q，但其中一些是重复的，例如{{1, 2}，{3}}和{{2, 1} {3}}。下一步是摆脱重复项。这有点棘手。解决方案如下。

更新

让我们定义一个结果集Q如果满足以下标准，则为唯一。

将Q定义为有序集合：{P1，P2，P3，...}，其中Pi也是元素的有序集合{Xi1，Xi2，...}。那么如果以下条件成立，则Q是唯一的：

每个集合Pi的元素按升序排列（即Xi1 <= Xi2 <= Xi3 ...）
按其大小的升序排列集合Pi（即sizeof(P1) <= sizeof(P2) <= sizeof(P3) ...）
按其最大值的升序排列集合Pi（即maximum_of(P1) <= maximum_of(P2) <= maximum_of(P3) ...），其中Pi的最大值是它的最大元素。

例如：

{{1,2}, {3,4}, {6,5}, {7,8}} - 不唯一

{{3,4}, {1,2}, {5,6}, {7,8}} - 不唯一

{{1,3}, {2,4}, {5,6}, {7,8}} - 唯一

{{1,2}, {3}, {4}, {5,6}, {7,8}} - 非唯一

- neleus

1

这将产生{{1,2},{3}}和{{2,1},{3}}，尽管它们实际上是相同的。 - sbeliakov

谢谢你的提示，我已经相应地更新了我的回答。 - neleus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lrrr · Accepted Answer

你可以使用递归的方法，我将向你展示如何从 {1, 2} 中找到 {1, 2, 3} 的答案。

对于一个包含 n 个元素的集合，可以通过解决没有第 n 个元素的问题来进行操作：

{{1 , 2}}
{{1}, {2}}

然后考虑您为n-1个元素创建的每个集合。并将第n个元素添加到这些集合的每个元素中，如下所示：

从{{1,2}}开始：

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

从{{1}, {2}}我们得到：

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

现在你可以看到我们已经解决了3个元素的问题。