finding all possible sum of two arrays element

Question

I have two arrays and i am trying to get all possible sum of each element with other element of two array and index of each element

int[] width = new int[2] {10,20 };
int[] height = new int[2] {30,40 };

result should like this (value / indexes)

10 width0

10+20 width0+width1

10+30 width0+height0

10+40 width0+height1

10+20+30 width0+width1+height0

10+20+40 width0+width1+height1

10+20+30+40 width0+width1+height0+height1

And so for each element in two array

I tried using permutation but I get other output

Looks like a permutation of a *single* list `{10, 20, 30, 40}` but why do you then need this strange indexes? — DrKoch, Feb 07 '15 at 17:22
possible duplicate of [All Possible Combinations of a list of Values in C#](http://stackoverflow.com/questions/7802822/all-possible-combinations-of-a-list-of-values-in-c-sharp) — HelloWorld, Feb 07 '15 at 17:36
Shouldn't 10+30+40 be there, too? Or am I missing something? — Mihai Caracostea, Feb 07 '15 at 17:49
@DrKoch iam searching for values and need to now where value come from or index of value component target=80 80 is height0+heght1+width0 — Sherif Elshahat, Feb 07 '15 at 18:48

Farhad Jabiyev · Accepted Answer · 2015-02-08T09:25:43.287

It is more easy to get all combinations from one array than two arrays. And as we see, you need to store indices and array names along with the value of the elements in collections. So, in my opinion the best option is to combine these two arrays in one dictionary, where the key will be the value of the numbers and the value will be [ArrayName + Index of item] (f.e width0, height1 and so on....)

So, let's combine these arrays in one dictionary:

int[] width = new int[2] { 10, 20 };
int[] height = new int[2] { 30, 40 };

var widthDictionary = width.ToList().Select((number, index) => new { index, number })
                           .ToDictionary(key => key.number, value => string.Format("width{0}", value.index));
var heightDictionary = height.ToList().Select((number, index) => new { index, number })
                           .ToDictionary(key => key.number, value => string.Format("height{0}", value.index));

// And here is the final dictionary
var totalDictionary = widthDictionary.Union(heightDictionary);

Then add this method to your class: (source)

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

Then send your dictionary as an argument to this method and project this collection as you want with the help of the Select() method:

 var sumOfCombinations = GetPowerSet(totalDictionary.ToList())
              .Where(x => x.Count() > 0)
              .Select(x => new
                        {
                           Numbers = x.Select(pair => pair.Key).ToList(),
                           DisplayValues = x.Select(pair => pair.Value).ToList()
                        })
              .ToList();

And at the end you can display expected result as this:

sumOfCombinations.ForEach(x =>
{
      x.Numbers.ForEach(number => Console.Write("{0} ", number));
      x.DisplayValues.ForEach(displayValue => Console.Write("{0} ", displayValue));
      Console.WriteLine();
});

And, the result is:

enter image description here

@SherifElshahat Thanks formarking as an answer. By the way, I have updated my answer as you wish. — Farhad Jabiyev, Feb 07 '15 at 20:03
@SherifElshahat I have changed my code slightly to fit your requirements . Because, there could be some performance problems in the last updated version. Good luck. — Farhad Jabiyev, Feb 08 '15 at 08:46
@FarhadJabiyev thanks Farhad very much this code is more smarter — Sherif Elshahat, Feb 08 '15 at 15:46

Brett Caswell · Answer 2 · 2015-02-07T20:45:58.840

This is a play off of @Farhad Jabiyev's answer.

Declares a class called IndexValuePair. and uses foreach on widthList and heightList. to populate the 'Index' property of item instance.

Note: Index is a string.

Class & Static Function

    public class IndexValuePair
    {
        public string Index {get;set;}
        public int Value {get;set;}
    }

    public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
    {
         return from m in Enumerable.Range(0, 1 << list.Count)
               select
                     from i in Enumerable.Range(0, list.Count)
                     where (m & (1 << i)) != 0
                     select list[i];
    }

Main (Console)

    static void Main(string[] args)
    {
        int[] width = new int[2] { 10, 20 };
        int[] height = new int[2] { 30, 40 };

        var wholeList = width.Select(val => new IndexValuePair() { Index = "width", Value = val }).ToList();
        var heightList = height.Select(val => new IndexValuePair() { Index = "height", Value = val }).ToList();

        var iteration = 0;
        wholeList.ForEach(ivp => { ivp.Index = ivp.Index + count; count = iteration + 1; });
        iteration = 0;
        heightList.ForEach(ipv => { ivp.Index = ivp.Index + count; count = iteration + 1; });

        wholeList.AddRange(heightList);

        var sumOfCombinations = GetPowerSet(wholeList).Where(x => x.Count() > 0)
             .Select(x => new { Combination = x.ToList(), Sum = x.Sum(ivp => ivp.Value) }).ToList();

        StringBuilder sb = new StringBuilder();
        sumOfCombinations.ForEach(ivp =>
        {
            ivp.Combination.ForEach(pair => sb.Append(string.Format("{0} ", pair.Value)));
            sb.Append(string.Format("= {0} = ", x.Sum));
            ivp.Combination.ForEach(pair=> sb.Append(string.Format("{0} + ", pair.Index)));
            sb.Length -= 3;
            Console.WriteLine(sb);
            sb.Clear();
        });

        var key = Console.ReadKey();
    }

finding all possible sum of two arrays element

2 Answers2

Class & Static Function

Main (Console)