如何获得子集的所有可能组合？
考虑这个List
List data = new List(); data.Add("Text1"); data.Add("Text2"); data.Add("Text3"); data.Add("Text4");
我遇到的问题是：如何获得列表子集的每个组合？ 有点像：
#Subset Dimension 4 Text1;Text2;Text3;Text4 #Subset Dimension 3 Text1;Text2;Text3; Text1;Text2;Text4; Text1;Text3;Text4; Text2;Text3;Text4; #Subset Dimension 2 Text1;Text2; Text1;Text3; Text1;Text4; Text2;Text3; Text2;Text4; #Subset Dimension 1 Text1; Text2; Text3; Text4;
我提出了一个很好的解决方案，值得在这里分享。
我认为，这个问题的答案需要一些性能测试。 我会试一试。 这是社区维基 ，随时更新它。
void PerfTest() { var list = Enumerable.Range(0, 21).ToList(); var t1 = GetDurationInMs(list.SubSets_LB); var t2 = GetDurationInMs(list.SubSets_Jodrell2); var t3 = GetDurationInMs(() => list.CalcCombinations(20)); Console.WriteLine("{0}\n{1}\n{2}", t1, t2, t3); } long GetDurationInMs(Func>> fxn) { fxn(); //JIT??? var count = 0; var sw = Stopwatch.StartNew(); foreach (var ss in fxn()) { count = ss.Sum(); } return sw.ElapsedMilliseconds; }
OUTPUT：
1281 1604 (_Jodrell not _Jodrell2) 6817
Jodrell的更新
我已经内置了发布模式，即优化。 当我通过Visual Studio运行时，我没有在1或2之间得到一致的偏差，但是在重复运行之后，LB的答案获胜，我得到了接近类似的答案，
1190 1260 more
但如果我从命令行运行测试工具，而不是通过Visual Studio运行，我得到的结果更像这样
987 879 still more
与Abaco的回答类似，不同的实施……
foreach (var ss in data.SubSets_LB()) { Console.WriteLine(String.Join("; ",ss)); } public static class SO_EXTENSIONS { public static IEnumerable> SubSets_LB( this IEnumerable enumerable) { List list = enumerable.ToList(); ulong upper = (ulong)1 << list.Count; for (ulong i = 0; i < upper; i++) { List l = new List (list.Count); for (int j = 0; j < sizeof(ulong) * 8; j++) { if (((ulong)1 << j) >= upper) break; if (((i >> j) & 1) == 1) { l.Add(list[j]); } } yield return l; } } }
编辑
我已经接受了性能挑战，接下来是我的合并，它取得了最好的答案。 在我的测试中，它似乎具有最佳性能。
public static IEnumerable> SubSets_Jodrell2( this IEnumerable source) { var list = source.ToList(); var limit = (ulong)(1 << list.Count); for (var i = limit; i > 0; i--) { yield return list.SubSet(i); } } private static IEnumerable SubSet ( this IList source, ulong bits) { for (var i = 0; i < source.Count; i++) { if (((bits >> i) & 1) == 1) { yield return source[i]; } } }
同样的想法，几乎与LB的答案相同，但我自己的解释。
我避免使用内部List和Math.Pow 。
public static IEnumerable> SubSets_Jodrell( this IEnumerable source) { var count = source.Count(); if (count > 64) { throw new OverflowException("Not Supported ..."); } var limit = (ulong)(1 << count) - 2; for (var i = limit; i > 0; i--) { yield return source.SubSet(i); } } private static IEnumerable SubSet ( this IEnumerable source, ulong bits) { var check = (ulong)1; foreach (var t in source) { if ((bits & check) > 0) { yield return t; } check <<= 1; } }
您会注意到这些方法在初始集中不能使用超过64个元素，但无论如何它开始需要一段时间。
我为列表开发了一个简单的ExtensionMethod：
/// /// Obtain all the combinations of the elements contained in a list /// /// Subset Dimension /// IEnumerable containing all the differents subsets public static IEnumerable> CalcCombinations(this List list, int subsetDimension) { //First of all we will create a binary matrix. The dimension of a single row //must be the dimension of list //on which we are working (we need a 0 or a 1 for every single element) so row //dimension is to obtain a row-length = list.count we have to //populate the matrix with the first 2^list.Count binary numbers int rowDimension = Convert.ToInt32(Math.Pow(2, list.Count)); //Now we start counting! We will fill our matrix with every number from 1 //(0 is meaningless) to rowDimension //we are creating binary mask, hence the name List combinationMasks = new List(); for (int i = 1; i < rowDimension; i++) { //I'll grab the binary rapresentation of the number string binaryString = Convert.ToString(i, 2); //I'll initialize an array of the apropriate dimension int[] mask = new int[list.Count]; //Now, we have to convert our string in a array of 0 and 1, so first we //obtain an array of int then we have to copy it inside our mask //(which have the appropriate dimension), the Reverse() //is used because of the behaviour of CopyTo() binaryString.Select(x => x == '0' ? 0 : 1).Reverse().ToArray().CopyTo(mask, 0); //Why should we keep masks of a dimension which isn't the one of the subset? // We have to filter it then! if (mask.Sum() == subsetDimension) combinationMasks.Add(mask); } //And now we apply the matrix to our list foreach (int[] mask in combinationMasks) { List temporaryList = new List (list); //Executes the cycle in reverse order to avoid index out of bound for (int iter = mask.Length - 1; iter >= 0; iter--) { //Whenever a 0 is found the correspondent item is removed from the list if (mask[iter] == 0) temporaryList.RemoveAt(iter); } yield return temporaryList; } } }
所以考虑问题中的例子：
# Row Dimension of 4 (list.Count) Binary Numbers to 2^4 # Binary Matrix 0 0 0 1 => skip 0 0 1 0 => skip [...] 0 1 1 1 => added // Text2;Text3;Text4 [...] 1 0 1 1 => added // Text1;Text3;Text4 1 1 0 0 => skip 1 1 0 1 => added // Text1;Text2;Text4 1 1 1 0 => added // Text1;Text2;Text3 1 1 1 1 => skip
希望这可以帮助别人:)
如果您需要澄清，或者您想要贡献，请随意添加答案或评论（哪一个更合适）。