最近看到如下问题:
尝试用C#解答这个问题
基本思路:
if(mask[i])
{
result.Add(collection.ElementAt(i));
}
- 对一个长度为
n
n
2
n
2^n
- 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
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