CODEWITHSUNDEEP
c#algorithm
Vishal Goyal
Vishal Goyal

Reputation: 190

find numbers that can be formed from sum of numbers from array in ascending order

I am trying to find the all possible values which are result of sum of values of given array. For example if given array is a = [50,100,120,260,360] then result will be [0,50,100,120,150,170,200,220,240,250,260,....]. How to implement it ?

I found one article realted to it but that is about to find the value which can't be formed using given array.

Find smallest number which can't be formed by values of given array

I found one more discussion related to something this but it is all about mathematics and I am still unable to understand how to implement it. You can have a look at it Find all possible values which can be formed using some values

Any algorithm or any code in C# could help.

Edit

We can use a single value many times.

more results could be 270 (50*1 + 100*1 + 120) , 300 (100*3), 310 (50 * 1 + 260 *1) etc.

Upvotes: 1

Views: 201

Answers (4)

Ivan Stoev
Ivan Stoev

Reputation: 205579

Here is the most efficient way to do that: 

public static class Algorithms
{
    public static IEnumerable<int> AllSums(this int[] source)
    {
        var indices = new int[source.Length];
        for (int count = 0, sum = 0, next = 0; ; next++)
        {
            if (next < source.Length)
            {
                indices[count++] = next;
                sum += source[next];
                yield return sum;
            }
            else
            {
                if (count == 0) break;
                next = indices[--count];
                sum -= source[next];
            }
        }
    }
}

Sample usage: 

var source = new[] { 50, 100, 120, 260, 360 };
Console.WriteLine("Source: {" + string.Join(", ", source.Select(n => n.ToString())) + "}");
Console.WriteLine("Sums: {" + string.Join(", ", source.AllSums().Select(n => n.ToString())) + "}");

or 

var source = new[] { 50, 100, 120, 260, 360 };
foreach (var sum in source.AllSums())
{
    // do something with the sum
}

Upvotes: 0

Enigmativity
Enigmativity

Reputation: 117027

This is what I use:

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null;
getAllSubsets = xs =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        : xs.Skip(1).Any()
            ? getAllSubsets(xs.Skip(1))
                .SelectMany(ys => new[] { ys, xs.Take(1).Concat(ys) })
            : new[] { Enumerable.Empty<int>(), xs.Take(1) };

Then you can do this:

var a = new [] { 50, 100, 120, 260, 360 };

Console.WriteLine(String.Join(", ", getAllSubsets(a).Select(x => x.Sum()).OrderBy(x => x)));

I get this:

0, 50, 100, 120, 150, 170, 220, 260, 270, 310, 360, 360, 380, 410, 410, 430, 460, 480, 480, 510, 530, 530, 580, 620, 630, 670, 720, 740, 770, 790, 840, 890

Knowing that values can be repeated then this is a way to go:

public IEnumerable<int> GenerateAllSums(int[] array)
{
    var buffer = new LinkedList<int>();
    buffer.AddFirst(0);
    while (true)
    {
        var first = buffer.First;
        var nexts = array.Select(a => first.Value + a);
        foreach (var next in nexts)
        {
            var x = buffer.First;
            while (x.Value < next)
            {
                x = x.Next;
                if (x == null)
                {
                    break;
                }
            }
            if (x == null)
            {
                buffer.AddLast(next);
            }
            else if (x.Value != next)
            {
                buffer.AddBefore(x, next);
            }
        }
        buffer.RemoveFirst();
        yield return first.Value;
    }
}

I can call it like so:

var a = new [] { 50, 100, 120, 260, 360, };

Console.WriteLine(String.Join(", ", GenerateAllSums(a).Take(100)));

It's important to note that the .Take(...) is now vital as the sequence is infinite.

Given the .Take(100) I get this result:

0, 50, 100, 120, 150, 170, 200, 220, 240, 250, 260, 270, 290, 300, 310, 320, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 1000, 1010, 1020, 1030, 1040, 1050, 1060, 1070, 1080, 1090, 1100, 1110, 1120, 1130, 1140, 1150, 1160, 1170

Upvotes: 3

Miyuru Ratnayake
Miyuru Ratnayake

Reputation: 456

 var repeat = 8;
 int[] source = new int[] {
     50, 100, 120, 260, 360
 };
 List < int > results = new List < int > ();
 for (int i = 0; i < Math.Pow(repeat, source.Length); i++) {
     var sum = 0;
     var bin = Convert.ToString(i, repeat);
     for (var j = 0; j < bin.Length; j++) {
         var pos = int.Parse(bin[j].ToString());
         if (0 < pos) {
             sum += source[j] * pos;
         }
     }
     results.Add(sum);
 }
 Console.WriteLine(results.Union(source).Distinct().OrderBy(x = > x));

Upvotes: 0

Abdul Rehman
Abdul Rehman

Reputation: 415

Find all subset of your array using something like this then sum, you will get all the possible values if you don't need the duplicated one remove them.

 int[] source = new int[] { 50,100,120,260,360 };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     int[] combination = new int[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

Upvotes: 1

Related Questions