Make sure that the list (or the list box of this list) of decimal values ​​can be equal to a certain

Question

Hi, I have a List<decimal> containing values ​​between] 0; one]. I want to check if the total (or subtotal) of these values ​​can equal 1 (or almost).

I can also use Linq functions to filter or manage the list.

Desired Results:

• A list containing {0.7, 0.7, 0.7} should return false;
• A list containing {0.7, 0.3, 0.7} should return true;
• A list containing {0.777777, 0.2, 0.1} should return false;
• A list containing {0.33333, 0.33333, 0.33333} should return true;
• A list containing {0.4, 0.5, 0.6, 0.3} should return true.

Obviously, I need something with minimal performance overhead.

Answer 1

UPDATED - now the amount does not repeat try this

 bool isClose(IEnumerable<decimal> list, decimal epislon) { return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon); } // Define other methods and classes here bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) { if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true; if (leftSum>1+epsilon) return false; if (leftSum+right.Sum()< 1-epsilon) return false; if (!right.Any()) return false; for (var i=0;i<right.Count();i++) { var skip=right.Skip(i); var newItem=skip.First(); if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true; } return false; } isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true 

EDIT 5th test

 isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true 

Answer 2

This is the problem of the sum of the subsets, a special case of a problem with a backpack. It's hard (NP-complete). The most famous algorithms have exponential complexity. However, there are approximate algorithms with polynomial complexity. They answer the question 'is there a subset that sums with 1 ± ε?'

• http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
• http://en.wikipedia.org/wiki/Subset_sum_problem
• Knuth TAOCP (possible)

Answer 3

Here's a pretty simple approach: niave, brute force. It will be inefficient, but I hope it is easier to understand.

 private const decimal threshold = .001M; public static bool CloseEnough(decimal first, decimal second, decimal threshold) { return Math.Abs(first - second) < threshold; } private static bool SubsetSum(List<decimal> data, int desiredSum) { int numIteratons = (int)Math.Pow(2, data.Count); for (int i = 1; i < numIteratons; i++) { decimal sum = 0; int mask = 1; for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++) { if ((i & mask) > 0) { sum += data[j]; } mask <<= 1; } if (CloseEnough(sum, desiredSum, threshold)) { return true; } } return false; } 

Answer 4

 public static bool SubListAddsTo(this IEnumerable<decimal> source, decimal target, decimal tolerance) { decimal lowtarget = target - tolerance; decimal hightarget = target + tolerance; HashSet<decimal> sums = new HashSet<decimal>(); sums.Add(0m); List<decimal> newSums = new List<decimal>(); foreach(decimal item in source) { foreach(decimal oldSum in sums) { decimal sum = oldSum + item; if (sum < lowtarget) { newSums.Add(sum);//keep trying } else if (sum < hightarget) { return true; } //else { do nothing, discard } } foreach (decimal newSum in newSums) { sums.Add(newSum); } newSums.Clear(); } return false; } 

Tested:

 List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m}; List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m}; List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m}; List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m }; List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m }; Console.WriteLine(list1.SubListAddsTo(1m, 0.001m)); //false Console.WriteLine(list2.SubListAddsTo(1m, 0.001m)); //true Console.WriteLine(list3.SubListAddsTo(1m, 0.001m)); //false Console.WriteLine(list4.SubListAddsTo(1m, 0.001m)); //true Console.WriteLine(list5.SubListAddsTo(1m, 0.001m)); //true 

Answer 5

edited: my source code did not allow approximation (0.9999 = 1).

In this case, the bitmap of the number of options is used to mask the values ​​in the original array in order to drag all the changes.

This is about 7.5 times faster than the accepted answer when testing on all five test cases in the millionth cycle (about 41 seconds versus about 5.5 seconds). This is about two times faster than David Blon's and about 15% faster than Servy sln.

  public static bool Test(decimal[] list, decimal epsilon) { var listLength = list.Length; var variations = (int)(Math.Pow(2, listLength) - 1); var bits = new bool[9]; for (var variation = variations; variation > 0; variation--) { decimal sum = 0; bits[1] = (variation & 1) == 1; bits[2] = (variation & 2) == 2; bits[3] = (variation & 4) == 4; bits[4] = (variation & 8) == 8; bits[5] = (variation & 16) == 16; bits[6] = (variation & 32) == 32; bits[7] = (variation & 64) == 64; bits[8] = (variation & 128) == 128; for (var bit = listLength; bit > 0; bit--) { if (bits[bit]) { sum += list[bit - 1]; } } if (Math.Abs(sum - 1) < epsilon) { return true; } } return false; } 

edit: this version of NewTest is 30% faster than higher, and more than ten times faster than the decision made. It removes the array construction to create a bitmask in favor of the Servy approach, in which the bulk of the improvement happens. It also removes the Math.Abs ​​call, which gave a minor improvement.

  private const decimal Epislon = 0.001m; private const decimal Upper = 1 + Epislon; private const decimal Lower = 1 - Epislon; private static bool NewTest(decimal[] list) { var listLength = list.Length; var variations = (int)(Math.Pow(2, listLength) - 1); for (var variation = variations; variation > 0; variation--) { decimal sum = 0; int mask = 1; for (var bit = listLength; bit > 0; bit--) { if ((variation & mask) == mask) { sum += list[bit - 1]; } mask <<= 1; } if (sum > Lower && sum < Upper) { return true; } } return false; }