score:3
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;
}
Source: stackoverflow.com
Related Query
- Verify if a list (or a sublist of that list) of decimal values can equal a certain sum
- Verify that a list has all the other list values
- Check a list of DTOs using linq to see if all values that exclude a particular value all equal the same thing
- Exclude list items that contain values from another list
- How can I set properties on all items from a linq query with values from another object that is also pulled from a query?
- Check if all values are equal in a list
- How to select values in list that are NOT IN a Table using EF Core?
- EF Code First: Methods that can translate to SQL
- How can I switch that code to use LINQ
- Use LINQ in order to select a list by matched sublist values in C#
- Calculating the sum of the values in a dictionary that exist in a generic list
- How can I get the average of the elements of a generic list that meet a criteria?
- How can I modify this C# code so that Visual Studio recognizes that I'm not an idiot?
- Linq: Is there a way to search a list of list of objects for values that match a condition?
- How can I select using LINQ for an entry that contains a LIST with more than one row?
- How to create a predicate that must meet two values with one being a list of values?
- How can i copy data table records of different field name based on mapping list evaluating condition on source data table?
- How can I sum values across a generic list using LINQ?
- How can I get a comma separated list of values from a List using LINQ?
- Linq for selecting elements from list 1 that exist on list 2 by comparsion between 2 properties values
- Using ASP.NET and MVC 3, how can I create hidden fields so that a List with an array as a value of each item in the list binds correctly?
- how to find items in list that their sum is less than or equal a number
- How can I retrieve all property values from a list of common objects?
- Get list of items where their ID is equal to some Values - linq c#
- Select all from one List, replace values that exist on another List
- Writing a LINQ statement that will add values for each list element
- LINQ retrieve values from a table that of which fields(of a certain column) are not equal of another table
- Sort array on one variable that can hold multiple values
- How can I make a list of the element numbers in a list that have a field that is not null?
- How can I use LINQ to retrieve entries that contain a specific property of a list within a list?
More Query from same tag
- Linq - how to loop a tree data structure to build a tree style object
- Compare 2 objects of the same type on the id field so I know to update or save the object
- LINQ VB.Net variable not declared error
- Unexpected result while generating string with Aggregate() in linq
- Why method does not traverse entire tree
- How can can i read values from linq query in AspNetCore?
- C# LINQ - Recognize unique index violation
- Compare two dictionaries and determine the minimum value using Linq
- Compare two lists to get waterfall chart data in LinQ
- Error initializing entity framework database sequence contains no matching elements
- Linq take 3 records from each category
- Linq to Join tables based on date in between
- how to clone/copy a datatable with only first n columns using linq
- Importing System.Linq solves "Class cannot be indexed" error
- FormViewModel in MVC for Relations
- Is there a way of adapting this function so it doesn't use LINQ? (convert byte array to string)
- How Can I dynamically create objects in C# Type and Name
- how to check all probabilities in an array
- Is the Specification Pattern obsolete when you can use Dynamic LINQ?
- Error message is given when creating a CSV from a List of Lists which are based on a Datamodel
- Initialize Object with LINQ to XML
- How to display the following result in WPF chart
- How do I use ."Include" on a Service Operation for ADO.Net Data Services
- What is the LINQ query to get a Cartesian Product even when one set is EMPTY?
- How to use a new select on the attribute of the first select?
- Entity Framework Relationships between two views
- Reference-Type Parameters and Linq
- How do I get a list of player without making its own class?
- How to flatten a list using linq c#
- AnyCase Searching Using LINQ