Geek asks and answers

Get all subsets of the collection.

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

For example, if I have a collection 10,20,30, I would 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 a collection can also be a collection of strings, for example, I want to create a generic method. This is what I developed 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 this 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 this method the following:

enter image description here

+3
source share
4 answers

This is a basic algorithm in which I used the technique below to make a single-user dictionary solver (newspaper).

n. 0 2^n. . i - 1, i - . 0 2^n .

: http://phoxis.org/2009/10/13/allcombgen/

+3

, , .

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;
    }
}
+2

, , , , , : http://praseedp.blogspot.com.br/2010/02/subset-generation-in-c.html

I :

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;            
    }
}

, -, :

        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();
        }

: O (2 ^ n), - 20 , 2 ^ 20 = 1048576 !

Edit: Servy sugest - Linq foreach, :

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();
        }
    }

:

        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);
        }

Servy .

+1

You do not want to return a list set, you want to use a java set type. The set already does part of what you are looking for, holding only one unique element of each type. Thus, you cannot add 20 twice, for example. This is an unordered type, so what you can do is write a combinatorial function that creates a set of sets and then returns a list that includes alist of them.

0
source

More articles:


All Articles