查找集合的所有子集 [英] Finding all the subsets of a set

问题描述

我需要一个算法来查找集合中元素数量 n 的所有子集。

  S = {1,2,3,4 ... n} 
  

编辑：我无法理解到目前为止提供的答案。

例如，

  S = {1,2,3,4,5} 
  

您如何知道 {1} 和 {1,2} 是子集？

可能有人帮我在c ++中使用一个简单的函数来查找{1,2,3,4,5}的子集

解决方案

这是很简单的递归。基本思想是，对于每个元素，子集集合可以被平均地分成包含该元素的集合和那些没有集合的子集，并且这两个集合在其他方面是相等的。

• 对于n = 1，子集集合是{{}，{1}}


• 1，...，n-1，并将其复制两份。对于其中一个，向每个子集添加n。





• {1}的子集集合是{{}，{1}}


• 2}，取{{}，{1}}，向每个子集添加2以获得{{2}，{1,2}}并取得与{{}，{1}}的并集以获得{{}， {1}，{2}，{1，2}}


• 重复此操作，直到达到n





I need an algorithm to find all of the subsets of a set where the number of elements in a set is n.

S={1,2,3,4...n}

Edit: I am having trouble understanding the answers provided so far. I would like to have step-by-step examples of how the answers work to find the subsets.

For example,

S={1,2,3,4,5}

How do you know {1} and {1,2} are subsets?

Could Someone help me with a simple function in c++ to find subsets of {1,2,3,4,5}

解决方案

It's very simple to do this recursively. The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.

• For n=1, the set of subsets is {{}, {1}}
• For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.

Edit To make it crystal clear:

• The set of subsets of {1} is {{}, {1}}
• For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
• Repeat till you reach n

这篇关于查找集合的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！