获取集合的所有子集 [英] Get all subsets of a collection

问题描述

我正在尝试创建一个将返回集合的所有子集的方法。

例如，如果我有一个集合 10,20 ，30 我想要得到以下输出

  return new List< List< int>> ;（）
 {
新列表< int>（）{10}，
新列表< int>（）{20}，
新列表< int>（）{ 30}，
新列表< int>（）{10,20}，
新列表< int> int（）{10,30}，
新列表< int> int（）{20 ，30}，
 //新列​​表< int>（）{20,10}，该子集已经存在
 //新列​​表< int>（）{30,20}，该子集已经存在
 new List< int>（）{10,20,30} 
}; 
  

因为该集合也可以是一个字符串集合，例如我想创建一个通用方法。这就是我根据此解决方案

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:

解决方案

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/

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