使用C#列出集合的所有子集

最近看到如下问题：

尝试用C#解答这个问题

基本思路：

• 一个由 n n n个元素组成的集合 A A A，有 2 n 2^n 2n个子集。
• 每一个具体的子集可以由一个掩码mask数组确定，表示每个元素是否包含。如果包含就把该元素添加到输出中去。

 if(mask[i])
 { 
     result.Add(collection.ElementAt(i));
 }

• 对一个长度为 n n n的集合，需要生成 2 n 2^n 2n个mask数组。
• mask数组示例：

var collection = { 1, 2, 3};
// mask数组一共有8个，分别是
var masks = new bool[][]
{ 
	[false,false,false],
	[false,false,true],
	[false,true,false],
	[false,true,true],
	[true,false,false],
	[true,false,true],
	[true,true,false],
	[true,true,true]
};
// 实际中可以用 List<BitArray>来代替bool[][].

• mask 数组的规律： 0 到 2 n − 1 0到2^n-1 0到2n−1的整数的二进制字符串就可以生成这个所谓的mask数组。

 static BitArray GetMaskByValue(int collectionLength, long maskValue)
 { 
 	// 将整数maskValue 转化成长度为collectionLength的字符数组。
     var masks = Convert.ToString(maskValue, 2).PadLeft(collectionLength, '0').ToCharArray();
	
	// 创建一个长度为collectionLength的BitArray。设默认值为false。
     var bitArray = new BitArray(collectionLength, false);
	
	// 如果字符是'1'就将对应的位置位true。
     for(int i = 0; i < collectionLength; i++)
     { 
         bitArray[i] = masks[i] == '1';
     }
     return bitArray;
 }

具体代码如下

class Program
   { 
       static void Main(string[] args)
       { 
           var collection = new int[] {  1,2,3,4,5 };
           EumerateSubCollections(collection); 
       }
		
		// 给定一个泛型集合，枚举所有的子集合。输出直接打印到控制台。
       static void EumerateSubCollections<T>(IEnumerable<T> collection)
       { 
           var masks = GenerateAllMasks(collection.Count());
           Console.WriteLine($"一共{masks.Count()}个子集");
           foreach(var mask in masks)
           { 
               var subCollection = GetSubCollection(collection, mask);
               Print(subCollection);
           }
       }
		
		// 一个集合的所有子集数量是 2^n 个，n指元素的个数。
		// 如果给定了一个mask，可以确定哪些元素包括，哪些不包括。
       static IEnumerable<T> GetSubCollection<T>(IEnumerable<T> collection, BitArray mask)
       { 
           if(mask.Length < collection.Count())
           { 
               return null;
           }
           List<T> result = new List<T>();
           for (int i = 0; i < collection.Count(); i++)
           { 
               if(mask[i])
               { 
                   result.Add(collection.ElementAt(i));
               }
           }
           return result;
       }
		
		// 生成所有的mask。mask可以认为是掩码。
       static IEnumerable<BitArray> GenerateAllMasks(int collectionLength)
       { 
           long count = (long)Math.Pow(2, collectionLength);
           var result = new List<BitArray>();
           for (long i = 0; i < count; i++)
           { 
               var bitArray = GetMaskByValue(collectionLength, i);
               result.Add(bitArray);
           }
           return result;
       }

		// 根据掩码值，创建一个mask数组。
       static BitArray GetMaskByValue(int collectionLength, long maskValue)
       { 
           var masks = Convert.ToString(maskValue, 2).PadLeft(collectionLength, '0').ToCharArray();
           var bitArray = new BitArray(collectionLength, false);
           for(int i = 0; i < collectionLength; i++)
           { 
               bitArray[i] = masks[i] == '1';
           }
           return bitArray;
       }

		// 对子集合进行打印。
       static void Print<T>(IEnumerable<T> collection)
       { 
           Console.Write("{");
           if(collection.Count() > 0)
           { 
               var builder = new StringBuilder();
               foreach (var element in collection)
               { 
                   builder.Append($"{element},");
               }
               builder.Remove(builder.Length - 1, 1);
               Console.Write(builder.ToString());
           }
           Console.WriteLine("}");
       }
   }

运行的输出

运行以上示例，可以得到以下输出：

本文地址：https://blog.csdn.net/apple_54477025/article/details/114002565