Csharp/C#教程:最小长度子集的有效幂算法分享


最小长度子集的有效幂算法

我正在使用以下C#函数来获取仅限于最小长度子集的powerset

string[] PowerSet(int min_len, string set) { IEnumerable<IEnumerable> seed = new List<IEnumerable>() { Enumerable.Empty() }; return set.Replace(" ", "") .Split(',') .Aggregate(seed, (a, b) => a.Concat(a.Select(x => x.Concat(new[] { b })))) .Where(subset => subset.Count() >= min_len) .Select(subset => string.Join(",", subset)) .ToArray(); } 

问题是当原始集很大时,即使最小长度也很大,算法也必须非常努力。

例如:

  PowerSet(27, "1,11,12,17,22,127,128,135,240,254,277,284,292,296,399,309,322,326,333,439,440,442,447,567,580,590,692,697"); 

应该很容易,但对于上述function来说太长了。 我正在寻找一个简洁的function修改,可以有效地处理这些情况。

快速浏览一下您的方法,其中一个低效率是创建了每个可能的子集,无论它是否有足够的成员来保证包含在有限的超集中。

请考虑实现以下扩展方法。 该方法可以根据其计数修剪掉一些不必要的子集,以避免过多的计算。

 public static List> PowerSet(List startingSet, int minSubsetSize) { List> subsetList = new List>(); //The set bits of each intermediate value represent unique //combinations from the startingSet. //We can start checking for combinations at (1<= minSubsetSize) { List subset = new List(setBitCount); for (int j = 0; j < startingSet.Count; j++) { //If the j'th bit in i is set, //then add the j'th element of the startingSet to this subset. if ((i & (1 << j)) != 0) { subset.Add(startingSet[j]); } } subsetList.Add(subset); } } return subsetList; } 

每个增量i的设置位数告诉您子集中将有多少成员。 如果没有足够的设置位,那么创建由位组合表示的子集的工作就没有意义了。 NumberOfSetBits可以通过多种方式实现。 请参见如何计算32位整数中的设置位数? 各种方法,解释和参考。 以下是从该问题中提取的一个例子。

 public static int NumberOfSetBits(int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } 

现在,虽然这个解决方案适用于您的示例,但我认为如果您将最小子集大小降低太多或继续增加startingSet的大小,您将遇到长运行时和内存问题。 如果您的问题中没有明确的要求,我无法判断此解决方案是否适合您和/或对您的预期输入案例范围是否安全。

如果您发现此解决方案仍然太慢,则可以将操作拆分为并行计算,可能使用PLINQfunction。

最后,如果你想用LINQ打扮扩展方法,它将如下所示。 但是,正如所写的那样,我认为如果不对其进行一些更改,您将会看到性能降低。

上述就是C#学习教程:最小长度子集的有效幂算法分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!

 public static IEnumerable> PowerSet(List startingSet, int minSubsetSize) { var startingSetIndexes = Enumerable.Range(0, startingSet.Count).ToList(); var candidates = Enumerable.Range((1 << minSubsetSize)-1, 1 << startingSet.Count) .Where(p => NumberOfSetBits(p) >= minSubsetSize) .ToList(); foreach (int p in candidates) { yield return startingSetIndexes.Where(setInd => (p & (1 << setInd)) != 0) .Select(setInd => startingSet[setInd]) .ToList(); } } 

www.ctvol.com true Article Csharp/C#教程:最小长度子集的有效幂算法分享

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/cdevelopment/1011639.html

(0)
上一篇 2021年12月30日 上午10:59
下一篇 2021年12月30日 上午11:00

精彩推荐