找出所有n个大小为k的子集，该子集包含n个大小不一的正整数(重复的未排序正整数) [英] Find all k-size subsets with sum s of an n-size bag of duplicate unsorted positive integers
问题描述
请注意，这对于 C#.NET 2.0 项目(不允许使用Linq )是必需的.
我知道这里已经提出了非常类似的问题，并且我已经产生了一些有效的代码(请参阅下文)，但仍然希望就在给定k和s条件的情况下如何使该算法更快地提出建议.
这是我到目前为止所学到的:动态编程是查找一个(不是全部)子集的最有效方法.如果我错了，请纠正我.有没有一种方法可以反复调用DP代码以产生更新的子集，直到用完重复设置的袋子用完了?
如果没有，那么是否有一种方法可以加速我下面的回溯递归算法，该算法可以产生我需要的算法，但是我想通过考虑s和k在O(2 ^ n)中运行?
这是我固定的一袋数字，永远不会改变，n = 114，数字范围是3到286:
int []数字=新的int []{7，286，200，176，120，165，206，75，129，109，123、111、43、52、99、128、111、110、98、135，112、78、118、64、77、227、93、88、69、60，34、30、73、54、45、83、182、88、75、85，54，53，89，59，37，35，38，29，18，45，60、49、62、55、78、96、29、22、24、1314、11、11、18、12、12、30、52、52、4428、28、20、56、40、31、50、40、46、4229、19、36、25、22、17、19、26、30、20，15、21、11、8、8、19、5、8、8、1111、8、3、9、5、4、7、3、6、3，5、4、5、6}; 要求
-
最大空间为2-3GB，但时间应为O(n ^ something)而不是(某物^ n).
-
不得对袋子进行分类，也不得删除重复的袋子.
-
结果应为匹配项中数字的索引子集，而不是数字本身(因为我们有重复项).
动态编程尝试
这里是C#动态编程版本，其内容来自stackoverflow.com上类似问题的答案:
使用系统；使用System.Collections.Generic;命名空间实用程序{公共静态类组合{私有静态Dictionary< int，bool>m_memo = new Dictionary< int，bool>();私有静态Dictionary< int，KeyValuePair< int，int>m_previous = new Dictionary< int，KeyValuePair< int，int>>();静态组合(){m_memo.Clear();m_previous.Clear();m_memo [0] = true;m_previous [0] =新的KeyValuePair< int，int>(-1，0);}公共静态布尔FindSubset(IList< int> set，int sum){//m_memo.Clear();//m_previous.Clear();//m_memo [0] = true;//m_previous [0] = new KeyValuePair< int，int>(-1，0);为(int i = 0; i< set.Count; ++ i){int num = set [i];对于(int s = sum; s> = num; --s){如果(m_memo.ContainsKey(s-num)&& m_memo [s-num] == true){m_memo [s] = true;如果(！m_previous.ContainsKey(s)){m_previous [s] =新的KeyValuePair< int，int>(i，num);}}}}返回m_memo.ContainsKey(sum)&&m_memo [sum];}公共静态IEnumerable< int>GetLastIndex(整数和){同时(m_previous [sum] .Key！= -1){收益回报率m_previous [sum] .Key;sum-= m_previous [sum] .Value;}}公共静态无效SubsetSumMain(string [] args){int []数字=新的int []{7，286，200，176，120，165，206，75，129，109，123、111、43、52、99、128、111、110、98、135，112、78、118、64、77、227、93、88、69、60，34、30、73、54、45、83、182、88、75、85，54，53，89，59，37，35，38，29，18，45，60、49、62、55、78、96、29、22、24、1314、11、11、18、12、12、30、52、52、4428、28、20、56、40、31、50、40、46、4229、19、36、25、22、17、19、26、30、20，15、21、11、8、8、19、5、8、8、1111、8、3、9、5、4、7、3、6、3，5、4、5、6};整数和= 400;//int size = 4;//不知道在动态编程中使用//调用动态编程如果(Numbers.FindSubset(numbers，sum)){foreach(Numbers.GetLastIndex(sum)中的int索引){Console.Write((index + 1)+." +数字[index] +"\ t");}Console.WriteLine();}Console.WriteLine();Console.ReadKey();}}} 递归编程尝试
这是C#递归编程版本，适用于stackoverflow.com上类似问题的答案:
使用系统；使用System.Collections.Generic;命名空间实用程序{公共静态类组合{私有静态int s_count = 0;公共静态int CountSubsets(int []数字，int索引，int当前，int和，int大小，List< int>结果){if((numbers.Length< = index)||(current> sum))返回0;if(结果==空)结果=新List< int>();List< int>temp = new List< int>(结果);如果(当前+数字[索引] ==总和){temp.Add(index);如果((size == 0)||(temp.Count == size)){s_count ++;}}否则，如果(当前+数字[索引]<和){temp.Add(index);CountSubsets(数字，索引+ 1，当前+数字[索引]，总和，大小，温度);}CountSubsets(数字，索引+ 1，当前，总和，大小，结果);返回s_count;}私有静态List< List< int>>m_subsets = new List< List< int>>>();公共静态List< List< int>>FindSubsets(int []数字，int索引，int当前，int和，int大小，List< int>结果){if((numbers.Length< = index)||(current> sum))返回m_subsets;if(结果==空)结果=新List< int>();List< int>temp = new List< int>(结果);如果(当前+数字[索引] ==总和){temp.Add(index);如果((size == 0)||(temp.Count == size)){m_subsets.Add(temp);}}否则，如果(当前+数字[索引]<和){temp.Add(index);FindSubsets(数字，索引+ 1，当前+数字[索引]，总和，大小，温度);}FindSubsets(数字，索引+ 1，当前，总和，大小，结果);返回m_subsets;}公共静态无效SubsetSumMain(string [] args){int []数字=新的int []{7，286，200，176，120，165，206，75，129，109，123、111、43、52、99、128、111、110、98、135，112、78、118、64、77、227、93、88、69、60，34、30、73、54、45、83、182、88、75、85，54，53，89，59，37，35，38，29，18，45，60、49、62、55、78、96、29、22、24、1314、11、11、18、12、12、30、52、52、4428、28、20、56、40、31、50、40、46、4229、19、36、25、22、17、19、26、30、20，15、21、11、8、8、19、5、8、8、1111、8、3、9、5、4、7、3、6、3，5、4、5、6};整数和= 17;整数大小= 2;//调用回溯递归编程Console.WriteLine("CountSubsets");int count = Numbers.CountSubsets(numbers，0，0，sum，size，null);Console.WriteLine("Count =" + count);Console.WriteLine();//调用回溯递归编程Console.WriteLine("FindSubsets");List< List< int>>子集= Numbers.FindSubsets(numbers，0，0，sum，size，null);对于(int i = 0; i< subsets.Count; i ++){if(subsets [i]！= null){Console.Write((i + 1).ToString()+:\ t");for(int j = 0; j 解决方案 我先前的答案是基于减少要检查的组合数量的原理.但是，对数组进行排序后，可以大大改善这一点.原理相似，但是由于解决方案完全不同，因此我决定将其放在单独的答案中.
我小心地仅使用.Net Framework 2.0功能.稍后可能会添加直观的说明，但注释应该足够.
类拼图{私有只读int [] _tailSums;公共只读SubsetElement []元素；公共只读int N;公共拼图(int []个数字){//设置N并生成Elements数组//(记住每个元素的原始索引)this.N =数字.长度;this.Elements = new SubsetElement [this.N];对于(var i = 0; i< this.N; i ++){this.Elements [i] = new SubsetElement(numbers [i]，i);}//按元素的Number值对其进行降序排序Array.Sort(this.Elements，(a，b)=> b.Number.CompareTo(a.Number));//保存尾数以允许按索引立即访问//允许通过索引= N的立即计算求和0this._tailSums = new int [this.N + 1];var sum = 0;对于(var i = this.N-1; i> = 0; i--){this._tailSums [i] = sum + = this.Elements [i] .Number;}}公共无效Solve(int s，Action< SubsetElement []>回调){对于(var k = 1; k< = this.N; k ++)this.Solve(k，s，callback);}公共无效Solve(int k，int s，Action< SubsetElement []>回调){this.ScanSubsets(0，k，s，new List< SubsetElement>()，回调);}私有void ScanSubsets(int startIndex，int k，int s，List< SubsetElement>子集，操作< SubsetElement []>cb){//没有更多的数字可添加，并且保证当前子集有效如果(k == 0){//使用当前子集进行回调cb(subset.ToArray());返回;}//求和最小的k个元素var minSubsetStartIndex = this.N-k;var minSum = this._tailSums [minSubssetStartIndex];//最小的总和大于期望的总和，//因此找不到有效的子集如果(minSum> s){返回;}//查找满足条件的最大数字//可以找到有效的子集minSum-= this.Elements [minSubsetStartIndex] .Number;//但是请记住满足条件的最后一个索引var minSubsetEndIndex = minSubsetStartIndex;而(minSubsetStartIndex> startIndex&minSum + this.Elements [minSubsetStartIndex-1] .Number< = s){minSubsetStartIndex--;}//在排序后的序列中找到第一个数字//我们刚刚找到的最大数字(如果重复)而(minSubsetStartIndex> startIndex&Elements [minSubsetStartIndex] == Elements [minSubsetStartIndex-1]){minSubsetStartIndex--;}//[minSubsetStartIndex .. maxSubsetEndIndex]是//完整范围，我们必须检查递归对于(varsubsetStartIndex = minSubsetStartIndex;子集开始索引< = minSubsetEndIndex;subsetStartIndex ++){//找到最大的和，即//k个第一个元素，从当前subsetStartIndex开始var maxSum = this._tailSums [subsetStartIndex]-this._tailSums [subsetStartIndex + k];//可能的最大和小于所需的和，//因此找不到有效的子集如果(maxSum< s){返回;}//将当前数字添加到子集var x = this.Elements [subsetStartIndex];子集.Add(x);//通过右边的子问题递归this.ScanSubsets(subsetStartIndex + 1，k-1，s-x.Number，子集，cb);//删除当前号码并继续循环subset.RemoveAt(subset.Count-1);}}公共密封类SubsetElement{公共只读int编号；公共只读int索引；公共SubsetElement(整数，整数索引){this.Number =数字；this.Index =索引；}公共重写字符串ToString(){返回string.Format("{0}({1})"，this.Number，this.Index);}}} 使用和性能测试:
private static void Main(){var sw = Stopwatch.StartNew();var Puzzle = new Puzzle(new []{7，286，200，176，120，165，206，75，129，109，123、111、43、52、99、128、111、110、98、135，112、78、118、64、77、227、93、88、69、60，34、30、73、54、45、83、182、88、75、85，54，53，89，59，37，35，38，29，18，45，60、49、62、55、78、96、29、22、24、1314、11、11、18、12、12、30、52、52、4428、28、20、56、40、31、50、40、46、4229、19、36、25、22、17、19、26、30、20，15、21、11、8、8、19、5、8、8、1111、8、3、9、5、4、7、3、6、3，5、4、5、6});puzzle.Solve(2，17，PuzzleOnSubsetFound);sw.Stop();Console.WriteLine(找到的子集:" + _subsetsCount);Console.WriteLine(sw.Elapsed);}私有静态int _subsetsCount;私有静态无效PuzzleOnSubsetFound(Puzzle.SubsetElement []子集){_subsetsCount ++;返回;//进行速度测试时跳过打印foreach(子集中的var el){Console.Write(el.ToString());Console.Write(");}Console.WriteLine();} 输出:
每行都是找到的子集，()中的数字是该子集中使用的数字的原始索引
14(60)3(107)
14(60)3(109)
14(60)3(102)
13(59)4(105)
13(59)4(111)
12(64)5(96)
12(64)5(104)
12(64)5(112)
12(64)5(110)
12(65)5(96)
12(65)5(104)
12(65)5(112)
12(65)5(110)
11(100)6(108)
11(100)6(113)
11(61)6(108)
11(61)6(113)
11(92)6(108)
11(92)6(113)
11(62)6(108)
11(62)6(113)
11(99)6(108)
11(99)6(113)
9(103)8(93)
9(103)8(94)
9(103)8(97)
9(103)8(98)
9(103)8(101)
找到的子集:28
00:00:00.0017020(不执行打印时测量)
k 越高，可以进行的截止就越多.这是您将看到主要性能差异的时候.当 s 升高时，您当前的代码(递归版本)的运行速度也会大大降低.
使用
k = 5，s = 60
您当前的代码:在 2.8602923 秒内找到了45070个子集
我的代码:在 0.0116727 秒内找到了45070个子集
那就是 99.6％速度改进
Please note that this is required for a C# .NET 2.0 project (Linq not allowed).
I know very similar questions have been asked here and I have already produce some working code (see below) but still would like an advice as to how to make the algorithm faster given k and s conditions.
This is what I've learnt so far: Dynamic programming is the most efficient way to finding ONE (not all) subsets. Please correct me if I am wrong. And is there a way of repeatedly calling the DP code to produce newer subsets till the bag (set with duplicates) is exhausted?
If not, then is there a way that may speed up the backtracking recursive algorithm I have below which does produce what I need but runs in O(2^n), I think, by taking s and k into account?
Here is my fixed bag of numbers that will NEVER change with n=114 and number range from 3 to 286:
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};
Requirements
Space limit to 2-3GB max but time should be O(n^something) not (something^n).
The bag must not be sorted and duplicate must not be removed.
The result should be the indices of the numbers in the matching subset, not the numbers themselves (as we have duplicates).
Dynamic Programming Attempt
Here is the C# dynamic programming version adapted from an answer to a similar question here on stackoverflow.com:
using System;
using System.Collections.Generic;
namespace Utilities
{
public static class Combinations
{
private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>();
private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>();
static Combinations()
{
m_memo.Clear();
m_previous.Clear();
m_memo[0] = true;
m_previous[0] = new KeyValuePair<int, int>(-1, 0);
}
public static bool FindSubset(IList<int> set, int sum)
{
//m_memo.Clear();
//m_previous.Clear();
//m_memo[0] = true;
//m_previous[0] = new KeyValuePair<int, int>(-1, 0);
for (int i = 0; i < set.Count; ++i)
{
int num = set[i];
for (int s = sum; s >= num; --s)
{
if (m_memo.ContainsKey(s - num) && m_memo[s - num] == true)
{
m_memo[s] = true;
if (!m_previous.ContainsKey(s))
{
m_previous[s] = new KeyValuePair<int, int>(i, num);
}
}
}
}
return m_memo.ContainsKey(sum) && m_memo[sum];
}
public static IEnumerable<int> GetLastIndex(int sum)
{
while (m_previous[sum].Key != -1)
{
yield return m_previous[sum].Key;
sum -= m_previous[sum].Value;
}
}
public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};
int sum = 400;
//int size = 4; // don't know to use in dynamic programming
// call dynamic programming
if (Numbers.FindSubset(numbers, sum))
{
foreach (int index in Numbers.GetLastIndex(sum))
{
Console.Write((index + 1) + "." + numbers[index] + "\t");
}
Console.WriteLine();
}
Console.WriteLine();
Console.ReadKey();
}
}
}
Recursive Programming Attempt
and Here is the C# recursive programming version adapted from an answer to a similar question here on stackoverflow.com:
using System;
using System.Collections.Generic;
namespace Utilities
{
public static class Combinations
{
private static int s_count = 0;
public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return 0;
if (result == null) result = new List<int>();
List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
temp.Add(index);
if ((size == 0) || (temp.Count == size))
{
s_count++;
}
}
else if (current + numbers[index] < sum)
{
temp.Add(index);
CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}
CountSubsets(numbers, index + 1, current, sum, size, result);
return s_count;
}
private static List<List<int>> m_subsets = new List<List<int>>();
public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return m_subsets;
if (result == null) result = new List<int>();
List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
temp.Add(index);
if ((size == 0) || (temp.Count == size))
{
m_subsets.Add(temp);
}
}
else if (current + numbers[index] < sum)
{
temp.Add(index);
FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}
FindSubsets(numbers, index + 1, current, sum, size, result);
return m_subsets;
}
public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};
int sum = 17;
int size = 2;
// call backtracking recursive programming
Console.WriteLine("CountSubsets");
int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null);
Console.WriteLine("Count = " + count);
Console.WriteLine();
// call backtracking recursive programming
Console.WriteLine("FindSubsets");
List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null);
for (int i = 0; i < subsets.Count; i++)
{
if (subsets[i] != null)
{
Console.Write((i + 1).ToString() + ":\t");
for (int j = 0; j < subsets[i].Count; j++)
{
int index = subsets[i][j];
Console.Write((index + 1) + "." + numbers[index] + " ");
}
Console.WriteLine();
}
}
Console.WriteLine("Count = " + subsets.Count);
Console.ReadKey();
}
}
}
Please let me know how to restrict the dynamic programming version to subsets of size k and if I can call it repeatedly so it returns different subsets on every call until there are no more matching subsets.
Also I am not sure where to initialize the memo of the DP algorithm. I did it in the static constructor which auto-runs when accessing any method. Is this the correct initialization place or does it need to be moved to inside the FindSunset() method [commented out]?
As for the recursive version, is it backtracking? and how can we speed it up. It works correctly and takes k and s into account but totally inefficient.
Let's make this thread the mother of all C# SubsetSum related questions!
My previous answer works on the principle of cutting off the number of combinations to check. But this can be improved significantly once you sort the array. The principle is similar, but since the solution is entirely different, I've decided to put it in a separate answer.
I was careful to use only .Net Framework 2.0 features. Might add a visual explanation later, but the comments should be enough.
class Puzzle
{
private readonly int[] _tailSums;
public readonly SubsetElement[] Elements;
public readonly int N;
public Puzzle(int[] numbers)
{
// Set N and make Elements array
// (to remember the original index of each element)
this.N = numbers.Length;
this.Elements = new SubsetElement[this.N];
for (var i = 0; i < this.N; i++)
{
this.Elements[i] = new SubsetElement(numbers[i], i);
}
// Sort Elements descendingly by their Number value
Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number));
// Save tail-sums to allow immediate access by index
// Allow immedate calculation by index = N, to sum 0
this._tailSums = new int[this.N + 1];
var sum = 0;
for (var i = this.N - 1; i >= 0; i--)
{
this._tailSums[i] = sum += this.Elements[i].Number;
}
}
public void Solve(int s, Action<SubsetElement[]> callback)
{
for (var k = 1; k <= this.N; k++)
this.Solve(k, s, callback);
}
public void Solve(int k, int s, Action<SubsetElement[]> callback)
{
this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback);
}
private void ScanSubsets(int startIndex, int k, int s,
List<SubsetElement> subset, Action<SubsetElement[]> cb)
{
// No more numbers to add, and current subset is guranteed to be valid
if (k == 0)
{
// Callback with current subset
cb(subset.ToArray());
return;
}
// Sum the smallest k elements
var minSubsetStartIndex = this.N - k;
var minSum = this._tailSums[minSubssetStartIndex];
// Smallest possible sum is greater than wanted sum,
// so a valid subset cannot be found
if (minSum > s)
{
return;
}
// Find largest number that satisfies the condition
// that a valid subset can be found
minSum -= this.Elements[minSubsetStartIndex].Number;
// But remember the last index that satisfies the condition
var minSubsetEndIndex = minSubsetStartIndex;
while (minSubsetStartIndex > startIndex &&
minSum + this.Elements[minSubsetStartIndex - 1].Number <= s)
{
minSubsetStartIndex--;
}
// Find the first number in the sorted sequence that is
// the largest number we just found (in case of duplicates)
while (minSubsetStartIndex > startIndex &&
Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1])
{
minSubsetStartIndex--;
}
// [minSubsetStartIndex .. maxSubsetEndIndex] is the
// full range we must check in recursion
for (var subsetStartIndex = minSubsetStartIndex;
subsetStartIndex <= minSubsetEndIndex;
subsetStartIndex++)
{
// Find the largest possible sum, which is the sum of the
// k first elements, starting at current subsetStartIndex
var maxSum = this._tailSums[subsetStartIndex] -
this._tailSums[subsetStartIndex + k];
// The largest possible sum is less than the wanted sum,
// so a valid subset cannot be found
if (maxSum < s)
{
return;
}
// Add current number to the subset
var x = this.Elements[subsetStartIndex];
subset.Add(x);
// Recurse through the sub-problem to the right
this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb);
// Remove current number and continue loop
subset.RemoveAt(subset.Count - 1);
}
}
public sealed class SubsetElement
{
public readonly int Number;
public readonly int Index;
public SubsetElement(int number, int index)
{
this.Number = number;
this.Index = index;
}
public override string ToString()
{
return string.Format("{0}({1})", this.Number, this.Index);
}
}
}
Usage and performance testing:
private static void Main()
{
var sw = Stopwatch.StartNew();
var puzzle = new Puzzle(new[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
});
puzzle.Solve(2, 17, PuzzleOnSubsetFound);
sw.Stop();
Console.WriteLine("Subsets found: " + _subsetsCount);
Console.WriteLine(sw.Elapsed);
}
private static int _subsetsCount;
private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset)
{
_subsetsCount++;
return; // Skip prints when speed-testing
foreach (var el in subset)
{
Console.Write(el.ToString());
Console.Write(" ");
}
Console.WriteLine();
}
Output:
Each line is a found subset, numbers in () are the original index of the number used in the subset
14(60) 3(107)
14(60) 3(109)
14(60) 3(102)
13(59) 4(105)
13(59) 4(111)
12(64) 5(96)
12(64) 5(104)
12(64) 5(112)
12(64) 5(110)
12(65) 5(96)
12(65) 5(104)
12(65) 5(112)
12(65) 5(110)
11(100) 6(108)
11(100) 6(113)
11(61) 6(108)
11(61) 6(113)
11(92) 6(108)
11(92) 6(113)
11(62) 6(108)
11(62) 6(113)
11(99) 6(108)
11(99) 6(113)
9(103) 8(93)
9(103) 8(94)
9(103) 8(97)
9(103) 8(98)
9(103) 8(101)
Subsets found: 28
00:00:00.0017020 (measured when no printing is performed)
The higher k is, the more cutoffs can be made. This is when you'll see the major performance difference. Your current code (the recursive version) also performs significantly slower when s is goes higher.
With
k=5,s=60
Your current code: found 45070 subsets in 2.8602923 seconds
My code: found 45070 subsets in 0.0116727 seconds
That is 99.6% speed improvement
这篇关于找出所有n个大小为k的子集，该子集包含n个大小不一的正整数(重复的未排序正整数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
