New User? Join Now Login Forgot Password?
Browse by Category
 Articles Games Algorithms Software
Browse by Language
 Java (3) J2ME (2) C# (18) VB.NET (1) JavaScript (1) Silverlight (16) C/C++ (1) Objective-C (2)
Browse Projects
 XamlQuery v1.2 YtoX Racketbot
Finding all Subsets of a Set  (74549 hits)
 Share this Article

Posted by Prabu Arumugam on Jul-18-2010
Languages: C#, Silverlight

This article explains how to find all subsets of a given set of items, without using recursion. A set contains 2N subsets, where N is the number or count of items in the set. The subsets are found using binary patterns (decimal to binary) of all the numbers in between 0 and (2N - 1).

The technique explained here is implemented in C# and Silverlight and a live demonstration is available below with full source code.

Finding Subsets Demo in Silverlight

The techniques explained are illustrated in this demo. The source code of the demo is available for download below.

Itemset and ItemsetCollection

Two simple helper classes namely Itemset and ItemsetCollection are created. An Itemset is just a list of strings; and the ItemsetCollection is list of itemsets. These classes improve the readability and helps to easily understand the source code.

These classes are defined as follows.

```public class Itemset : List<string>
{
}

public class ItemsetCollection : List<Itemset>
{
}
```

Creating and initializing an Itemset is very similar to the initialization of a string array.

```Itemset i1 = new Itemset() { "1", "2", "3", "4", "5" };
```

Finding Subsets without Recursion

There will be 2N subsets for a given set, where N is the cardinality (number of items) of that set. For example, there will be 25 = 32 subsets for the set {1, 2, 3, 4, 5}. The binary representation of each number 'i' in the range 0 to (2N - 1) is used to find the corresponding ith subset.

Each '1' in the binary representation indicates an item in that position. For example, the binary representation of number 5 is 00101 which in turn represents the subset {3, 5} of the set {1, 2, 3, 4, 5}.

```public static ItemsetCollection FindAllSubsets(Itemset itemset)
{
ItemsetCollection allSubsets = new ItemsetCollection();

int subsetCount = (int)Math.Pow(2, itemset.Count);
for (int i = 0; i < subsetCount; i++)
{
Itemset subset = new Itemset();
for (int bitIndex = 0; bitIndex < itemset.Count; bitIndex++)
{
if (GetBit(i, bitIndex) == 1)
{
subset.Add(itemset[bitIndex]);
}
}

allSubsets.Add(subset);
}

return (allSubsets);
}
```

The GetBit() function is used to find a bit in the binary representation of the corresponding decimal number.

```public static int GetBit(int value, int position)
{
int bit = value & (int)Math.Pow(2, position);
return (bit > 0 ? 1 : 0);
}
```

Downloads for this article
File Language Tools
Subsets-Demo-Source  24.86 kb  (323 downloads) C#, Silverlight 3 Visual Studio 2008

Share this Article

Comments on this Article
 Comment by narendra ilam on Jul-08-2016try to keep c program in simple manner Comment by sara on Jun-03-2014tnx for sharing. but i have a question: how can perform the subset operation using bit fields and hashtree structure? plz help me Comment by Qu?c Tân on Jun-03-2014If i use double values. How can i do that! Comment by cincoutprabu on Oct-11-2013The answer lies in the article itself. There will be 2^n subsets in a set of n elements. So, there will be 2^20 = 1048576 subsets for a set of 20 elements. Comment by annominus on Oct-10-2013if we have to find how many subsets there can be in a set of 20 elements but do not have the actual numbers in the set how do we figure it out???????!!!!!!!! Comment by hawa dafuah on Feb-04-2013pls. help becuse i cann't really understand this thing Comment by tuananhk43 on Jun-02-2012Can you edit code? I want subsets that subset cout equa k I edit code public static ItemsetCollection FindAllSubsets(Itemset itemset, int k) { ItemsetCollection allSubsets = new ItemsetCollection(); int subsetCount = (int)Math.Pow(2, itemset.Count); for (int i = 0; i < subsetCount; i++) { Itemset subset = new Itemset(); for (int bitIndex = 0; bitIndex < itemset.Count; bitIndex++) { if (GetBit(i, bitIndex) == 1) { subset.Add(itemset[bitIndex]); } } if (subset.Count == k) allSubsets.Add(subset); } return (allSubsets); } Plaese comment Comment by mihai on Feb-17-2012I think it's a bug, the subsets contain an item many times, and I think that's not the idea. Comment by Tester on Jan-28-2012Good One! :-)
Post your comment here
 Your Name Your Email Comment Post Comment
Most Viewed Articles
 Apriori Algorithm K-Means Algorithm Finding all Subsets of a Set Expression Evaluation Image Denoising PGM Image Manipulation Dijkstra's Path Finding Dynamic Silverlight DataGrid Silverlight Bullets & Indenting Motion Detection Algorithm
Recent Articles
 Motion Detection Algorithm Blowfish Algorithm for iPhone Connected Sets Labeling DotGame in C using Mouse Silverlight Bullets & Indenting iPhone Expression Calculator 8pen Demo Dijkstra's Path Finding BrainBoard in Silverlight Drawing in Silverlight

 About Terms Contact