使用C#列出集合的所有子集
程序员文章站
2022-03-13 08:28:42
最近看到如下问题:尝试用C#解答这个问题基本思路:一个由nnn个元素组成的集合AAA,有2n2^n2n个子集。每一个具体的子集可以由一个掩码mask数组确定,表示每个每个元素是否包含。如果包含就把该元素添加到输出中去。 if(mask[i]) { result.Add(collection.ElementAt(i)); }具体代码如下class Program { static void Main(string[] args) {...
最近看到如下问题:
尝试用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
上一篇: 记一些CSS属性总结(二)