score:3

Accepted answer

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

score:0

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

score:0

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;
    }

score:1

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±ε ?'

score:1

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;
}

Related Query

More Query from same tag