Verify if a list (or a sublist of that list) of decimal values can equal a certain sum

Question

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

I can also use Linq functions to filter or manipulate 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'll want something with the lowest performance cost possible.

Answer 1

UPDATED -- now doesn't repetively sum 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 subset sum problem, a special case of the knapsack problem. It's hard (NP-complete). The best known algorithms have exponential complexity. However there are approximate algorithms with polynomial complexity. These answer the question 'is there a subset that sums to 1±ε ?'

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

Answer 3

Here is a rather straightforward, niave, brute force approach. It won't be efficient, but hopefully it's 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 by:

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 original code didn't allow for the approximation (0.9999 = 1).

This uses a bitmap of the number of variations to mask the values in the source array in order to brute force all of the variations.

This is about 7.5 times faster than the accepted answer when tested on all five test cases in a million count loop (about 41 seconds vs about 5.5 seconds). It is about twice as fast as David B's sln and about 15% faster than Servy's 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 NewTest version is 30% faster than the above version and is over ten times faster than the accepted solution. It removes building the array for coming up with the bitmask in favour of Servy's approach which is where the bulk of the improvement comes from. It also removes the Math.Abs call which gave marginal 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;
    }