1

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.

John
  • 423
  • 4
  • 15
  • 2
    Please show us your existing code. _I also find the way you have expressed your `result` to be confusing._ – mjwills Aug 30 '17 at 13:23
  • the random values which i have mentioned at the first is the decimal array which i ll be passing for set, the second parameter sum is the exact value as in example 319 will be passed through this and the startpercent and endpercent denotes the range – John Aug 30 '17 at 14:04
  • `286-300=16` Er, no it doesn't. It is -`14` Therefore that should not be one of your expected results. However, `4, 50, 20, 99, 97` adds up to 270, which gives a difference of 30, so that *should* be one of the outputs. – Matthew Watson Aug 30 '17 at 14:05
  • at each iteration summing each values with one another and checking whether the difference between the 319 and the summed values is within the range and if condition satisfies returning the list – John Aug 30 '17 at 14:07
  • sorry, 286-300 is typo error please consider it as 284 then the differnce would be 16 which satisfies the condition – John Aug 30 '17 at 14:08
  • i am trying to explain that it is missing few sequence not returning everything – John Aug 30 '17 at 14:09

1 Answers1

3

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:

  • Select i from 1 to 2^N-1 where N is the number of items to combine.
  • For each bit set in 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
Matthew Watson
  • 104,400
  • 10
  • 158
  • 276