Get all subsets of a collection

Question

I am trying to create a method that will return all subsets of a set.

For example if I have the collection 10,20,30 I will like to get the following output

        return new List<List<int>>()
        {
            new List<int>(){10},
            new List<int>(){20},
            new List<int>(){30},
            new List<int>(){10,20},
            new List<int>(){10,30},
            new List<int>(){20,30},
            //new List<int>(){20,10}, that substet already exists
            // new List<int>(){30,20}, that subset already exists
            new List<int>(){10,20,30}
        };

because the collection can also be a collection of strings for instance I want to create a generic method. This is what I have worked out based on this solution.

    static void Main(string[] args)
    {
        Foo<int>(new int[] { 10, 20, 30});
    }

    static List<List<T>> Foo<T>(T[] set)
    {

        // Init list
        List<List<T>> subsets = new List<List<T>>();

        // Loop over individual elements
        for (int i = 1; i < set.Length; i++)
        {
            subsets.Add(new List<T>(){set[i - 1]});

            List<List<T>> newSubsets = new List<List<T>>();

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                var tempList = new List<T>();
                tempList.Add(subsets[j][0]);
                tempList.Add(subsets[i][0]);
                var newSubset = tempList;
                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

        // Add in the last element
        //subsets.Add(set[set.Length - 1]);
        //subsets.Sort();

        //Console.WriteLine(string.Join(Environment.NewLine, subsets));
        return null;
    }

---

Edit

Sorry that is wrong I still get duplicates...

    static List<List<T>> GetSubsets<T>(IEnumerable<T> Set)
    {
        var set = Set.ToList<T>();

        // Init list
        List<List<T>> subsets = new List<List<T>>();

        subsets.Add(new List<T>()); // add the empty set

        // Loop over individual elements
        for (int i = 1; i < set.Count; i++)
        {
            subsets.Add(new List<T>(){set[i - 1]});

            List<List<T>> newSubsets = new List<List<T>>();

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                var newSubset = new List<T>();
                foreach(var temp in subsets[j])
                    newSubset.Add(temp);

                newSubset.Add(set[i]);


                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

        // Add in the last element
        subsets.Add(new List<T>(){set[set.Count - 1]});
        //subsets.Sort();

        return subsets;
    }

Then I could call that method as:

Answer 1

This is a basic algorithm which i used the below technique to make a single player scrabble word solver (the newspaper ones).

Let your set have n elements. Increment an integer starting from 0 to 2^n. For each generater number bitmask each position of the integer. If the i th position of the integer is 1 then select the i th element of the set. For each generated integer from 0 to 2^n doing the above bitmasting and selection will get you all the subsets.

Here is a post: http://phoxis.org/2009/10/13/allcombgen/

Answer 2

Here is an adaptation of the code provided by Marvin Mendes in this answer but refactored into a single method with an iterator block.

public static IEnumerable<IEnumerable<T>> Subsets<T>(IEnumerable<T> source)
{
    List<T> list = source.ToList();
    int length = list.Count;
    int max = (int)Math.Pow(2, list.Count);

    for (int count = 0; count < max; count++)
    {
        List<T> subset = new List<T>();
        uint rs = 0;
        while (rs < length)
        {
            if ((count & (1u << (int)rs)) > 0)
            {
                subset.Add(list[(int)rs]);
            }
            rs++;
        }
        yield return subset;
    }
}

Answer 3

I know that this question is a little old but i was looking for a answer and dont find any good here, so i want to share this solution that is an adaptation found in this blog: http://praseedp.blogspot.com.br/2010/02/subset-generation-in-c.html

I Only transform the class into a generic class:

public class SubSet<T>
{
    private IList<T> _list;
    private int _length;
    private int _max;
    private int _count;

    public SubSet(IList<T> list)
    {
        if (list== null)
            throw new ArgumentNullException("lista");
        _list = list;
        _length = _list.Count;
        _count = 0;
        _max = (int)Math.Pow(2, _length);
    }


    public IList<T> Next()
    {
        if (_count == _max)
        {
            return null;
        }
        uint rs = 0;

        IList<T> l = new List<T>();            

        while (rs < _length)
        {
            if ((_count & (1u << (int)rs)) > 0)
            {
                l.Add(_list[(int)rs]);                    
            }
            rs++;
        }
        _count++;
        return l;            
    }
}

To use this code you can do like something that:

        List<string> lst = new List<string>();

        lst.AddRange(new string[] {"A", "B", "C" });

        SubSet<string> subs = new SubSet<string>(lst);

        IList<string> l = subs.Next();

        while (l != null)
        {

            DoSomething(l);
            l = subs.Next();
        }

Just remember: this code still be an O(2^n) and if you pass something like 20 elements in the list you will get 2^20= 1048576 subsets!

Edit: As Servy sugest i add an implementation with interator block to use with Linq an foreach, the new class is like this:

private class SubSet<T> : IEnumerable<IEnumerable<T>>
    {
        private IList<T> _list;
        private int _length;
        private int _max;
        private int _count;

        public SubSet(IEnumerable<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            _list = new List<T>(list);
            _length = _list.Count;
            _count = 0;
            _max = (int)Math.Pow(2, _length);
        }

        public int Count
        {
            get { return _max; }
        }



        private IList<T> Next()
        {
            if (_count == _max)
            {
                return null;
            }
            uint rs = 0;

            IList<T> l = new List<T>();

            while (rs < _length)
            {
                if ((_count & (1u << (int)rs)) > 0)
                {
                    l.Add(_list[(int)rs]);
                }
                rs++;
            }
            _count++;
            return l;
        }

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            IList<T> subset;
            while ((subset = Next()) != null)
            {
                yield return subset;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

and you now can use it like this:

        List<string> lst = new List<string>();

        lst.AddRange(new string[] {"A", "B", "C" });

        SubSet<string> subs = new SubSet<string>(lst);

        foreach(IList<string> l in subs)
        {
            DoSomething(l);
        }

Thanks Servy for the advice.

Answer 4

It Doesn't give duplicate value;

Don't add a value of the int array at the start of the subsets

Correct program is as follows:

class Program
    {
        static HashSet<List<int>> SubsetMaker(int[] a, int sum)
        {
            var set = a.ToList<int>();
            HashSet<List<int>> subsets = new HashSet<List<int>>();
            subsets.Add(new List<int>());
            for (int i =0;i<set.Count;i++)
            {
                //subsets.Add(new List<int>() { set[i]});
                HashSet<List<int>> newSubsets = new HashSet<List<int>>();
                for (int j = 0; j < subsets.Count; j++)
                {
                   var newSubset = new List<int>();
                   foreach (var temp in subsets.ElementAt(j))
                   {
                      newSubset.Add(temp);


                    }
                    newSubset.Add(set[i]);
                    newSubsets.Add(newSubset);

                }
                Console.WriteLine("New Subset");
                foreach (var t in newSubsets)
                {
                    var temp = string.Join<int>(",", t);
                    temp = "{" + temp + "}";
                    Console.WriteLine(temp);
                }
                Console.ReadLine();

                subsets.UnionWith(newSubsets);
            }
            //subsets.Add(new List<int>() { set[set.Count - 1] });
            //subsets=subsets.;
            return subsets;

        }
        static void Main(string[] args)
        {
            int[] b = new int[] { 1,2,3 };
            int suma = 6;
            var test = SubsetMaker(b, suma);
            Console.WriteLine("Printing final set...");
            foreach (var t in test)
            {
                var temp = string.Join<int>(",", t);
                temp = "{" + temp + "}";
                Console.WriteLine(temp);
            }
            Console.ReadLine();

        }
    }

Answer 5

You don't want to return a set of lists, you want to use java's set type. Set already does part of what you are looking for by holding only one unique element of each type. So you can't add 20 twice for instance. It is an unordered type, so what you might do is write a combinatoric function that creates a bunch of sets and then return a list that includes alist of those.

Answer 6

Get all subsets of a collection of a specific subsetlength:

    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetPermutations(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) != 0)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }

    public static IEnumerable<IEnumerable<T>> GetOrderedSubSets<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetOrderedSubSets(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) == -1)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }

Testcode:

        List<int> set = new List<int> { 1, 2, 3 };
        foreach (var x in GetPermutations(set, 3))
        {
            Console.WriteLine(string.Join(", ", x));
        }
        Console.WriteLine();
        foreach (var x in GetPermutations(set, 2))
        {
            Console.WriteLine(string.Join(", ", x));
        }
        Console.WriteLine();
        foreach (var x in GetOrderedSubSets(set, 2))
        {
            Console.WriteLine(string.Join(", ", x));
        }

Test results:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

1, 2
1, 3
2, 1
2, 3
3, 1
3, 2

1, 2
1, 3
2, 3

Answer 7

A simple algorithm based upon recursion:

private static List<List<int>> GetPowerList(List<int> a)
    {
        int n = a.Count;
        var sublists = new List<List<int>>() { new List<int>() };
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                var first = a[i];
                var last = a[j];
                if ((j - i) > 1)
                {
                    sublists.AddRange(GetPowerList(a
                        .GetRange(i + 1, j - i - 1))
                        .Select(l => l
                        .Prepend(first)
                        .Append(last).ToList()));
                }
                else sublists.Add(a.GetRange(i,j - i + 1));
            }
        }
        return sublists;
    }