New User?   Join Now     Login            Forgot Password?    
Browse by Category
Articles
Games
Algorithms
Software
Browse Projects
XamlQuery v1.2
YtoX
Browse Topics
Finding all Subsets of a Set  (29175 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  (255 downloads) C#, Silverlight 3 Visual Studio 2008

 Share this Article

 Comments on this Article
Comment by sara on Jun-03-2014
tnx 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-2014
If i use double values. How can i do that!
Comment by cincoutprabu on Oct-11-2013
The 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-2013
if 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-2013
pls. help becuse i cann't really understand this thing
Comment by tuananhk43 on Jun-02-2012
Can 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-2012
I 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-2012
Good One! :-)
 Post your comment here
Your Name
Your Email
Comment
Post Comment

About About      Terms Terms      Contact Contact
codeding on Facebook Facebook      codeding on Twitter Twitter