I have a list of random values as below
319, 4, 90, 50, 20, 99, 500, 95, 900
and i have to find a values which sum is within selected range say 5% to 10%.
for example if the number is 300 and the range was 5% to 10%
then the difference should be in the range 15 to 30
then the list which satisfy this condition is
319 => 319-300=-19 which nearest to 300 and difference within range 5% to 10% 319,4 => 319+4=323 => 323-300=-23 which nearest to 300 and difference within range 5% to 10% 90,99,97 => 90+99+95=284 => 284-300=16 which nearest to 300 and difference within range 5% to 10%
the result will be
319,
319,4
90,99,95
i have tried with modifying the recursive algorithm (Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number) but it is able to return only few matched sequence and not all.
Code:
public static IEnumerable<string> GetSequence(decimal[] set, decimal? sum, decimal? startPercent, decimal? endPercent, string values = "")
{
for (int i = 0; i < set.Length; i++)
{
decimal? left = sum - set[i];
string vals = set[i] + "," + values;
if (Math.Abs(decimal.Parse(left.ToString())) >= startPercent && Math.Abs(decimal.Parse(left.ToString())) <= endPercent)
{
yield return vals;
}
else
{
decimal[] possible = set.Take(i).Where(n => n <= sum).ToArray();
if (possible.Length > 0)
{
foreach (string s in GetSequence(possible, left, startPercent, endPercent, vals))
{
yield return s;
}
}
}
}
}
Could anybody help me with this.
Possibly a better approach is to generate all possible combinations using code like so:
public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> items)
{
return Combinations(items.Count).Select(comb => comb.Select(index => items[index]));
}
public static IEnumerable<IEnumerable<int>> Combinations(int n)
{
long m = 1 << n;
for (long i = 1; i < m; ++i)
yield return bitIndices((uint)i);
}
static IEnumerable<int> bitIndices(uint n)
{
uint mask = 1;
for (int bit = 0; bit < 32; ++bit, mask <<= 1)
if ((n & mask) != 0)
yield return bit;
}
Then you can write a method to sum each possible combination:
static IEnumerable<(int Sum, List<int> Values)> SummedCombinations(IList<int> values)
{
return
Combinations(values)
.Select(comb => comb.ToList())
.Select(comb => (comb.Sum(), comb));
}
Then you can write a method to find all the combinations where the sum matches the range you're looking for:
static IEnumerable<List<int>> FindMatches(IList<int> values, int target, int toleranceLow, int toleranceHigh)
{
int minDiff = (target * toleranceLow) / 100;
int maxDiff = (target * toleranceHigh) / 100;
foreach (var sum in SummedCombinations(values))
{
int diff = Math.Abs(sum.Sum - target);
if (minDiff <= diff && diff <= maxDiff)
yield return sum.Values;
}
}
Putting this all together into a compilable console app:
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main()
{
int[] values = {319, 4, 90, 50, 20, 99, 500, 95, 900};
foreach (var combination in FindMatches(values, 300, 5, 10))
{
Console.WriteLine(string.Join(", ", combination));
}
}
static IEnumerable<List<int>> FindMatches(IList<int> values, int target, int toleranceLow, int toleranceHigh)
{
int minDiff = (target * toleranceLow) / 100;
int maxDiff = (target * toleranceHigh) / 100;
foreach (var sum in SummedCombinations(values))
{
int diff = Math.Abs(sum.Sum - target);
if (minDiff <= diff && diff <= maxDiff)
yield return sum.Values;
}
}
static IEnumerable<(int Sum, List<int> Values)> SummedCombinations(IList<int> values)
{
return
Combinations(values)
.Select(comb => comb.ToList())
.Select(comb => (comb.Sum(), comb));
}
public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> items)
{
return Combinations(items.Count).Select(comb => comb.Select(index => items[index]));
}
public static IEnumerable<IEnumerable<int>> Combinations(int n)
{
long m = 1 << n;
for (long i = 1; i < m; ++i)
yield return bitIndices((uint)i);
}
static IEnumerable<int> bitIndices(uint n)
{
uint mask = 1;
for (int bit = 0; bit < 32; ++bit, mask <<= 1)
if ((n & mask) != 0)
yield return bit;
}
}
}
This outputs:
319
319, 4
90, 99, 95
Which is your expected output.
Note: The code above is using C# 7 tuples - if you are using an earlier version you'll have to change FindMatches() and SummedCombinations() to:
static IEnumerable<List<int>> FindMatches(IList<int> values, int target, int toleranceLow, int toleranceHigh)
{
int minDiff = (target * toleranceLow) / 100;
int maxDiff = (target * toleranceHigh) / 100;
foreach (var sum in SummedCombinations(values))
{
int diff = Math.Abs(sum.Item1 - target);
if (minDiff <= diff && diff <= maxDiff)
yield return sum.Item2;
}
}
static IEnumerable<Tuple<int, List<int>>> SummedCombinations(IList<int> values)
{
return
Combinations(values)
.Select(comb => comb.ToList())
.Select(comb => Tuple.Create(comb.Sum(), comb));
}
Explanation of the Combinations part
The combinations work as follows:
i from 1 to 2^N-1 where N is the number of items to combine.i, return the item from the corresponding location in the input values.So for example if you have 3 values; A, B and C:
i will go from 1 to (2^3-1) = 7.
Look at the binary values we will get for 1..7, and look at the corresponding elements of the A, B, C input:
C B A (Input)
2 1 0 (Bit number, i.e. power of two)
---------------------------------------
0 0 1 [1] = A
0 1 0 [2] = B
0 1 1 [3] = A B
1 0 0 [4] = C
1 0 1 [5] = A C
1 1 0 [5] = B C
1 1 1 [6] = A B C
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments