获取集合的所有子集

本文介绍了获取集合的所有子集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

例如，如果我有一个集合 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: phoxis/2009/10/13/allcombgen/