c# How to set the maximum number when do the find all possible combinations of numbers to reach a given sum

Question

Im new to c# then my supervisor ask me to find all possible combination of given set of numbers and I must set the maximum for the combinations. The combinations I already get but for set the maximum number can't be done.The maximum number is for the combinations. From my image it have 5,4 and 3 row that is all the possible combinations. but I just want to set only output that have 3 row only will be display. I have tried many way but still can't get it. Sorry for my bad english.

Here are the code.

class Program
{
static void Main(string[] args)
{

    string input;
    decimal goal;
    decimal element;
    int max = 2;

    do
    {
        Console.WriteLine("Please enter the target:");
        input = Console.ReadLine();
    }
    while (!decimal.TryParse(input, out goal));

    Console.WriteLine("Please enter the numbers (separat`enter code here`ed by spaces)");
    input = Console.ReadLine();
    string[] elementsText = input.Split(' ');
    List<decimal> elementsList = new List<decimal>();
    foreach (string elementText in elementsText)
    {
        if (decimal.TryParse(elementText, out element))
        {
            elementsList.Add(element);
        }
    }

    Solver solver = new Solver();
    List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());



    //foreach (List<decimal> result in results)
    //{
    //    foreach (decimal value in result)
    //    {
    //        Console.Write("{0}\t", value);
    //    }
    //    Console.WriteLine();
    //}


    for (int i = 0; i <= results.Count; i++)
    {

        int x = results.SelectMany(list => list).Distinct().Count();

        if (x <= max)
        {

            for (int j = 0; j <= max; j++)
            {
                Console.Write("{0}\t", results[i][j]);
            }
            Console.WriteLine();
        }
    }


    Console.ReadLine();
}
}

here is the ouput

I just want to know how to set the maximum num only. Thank you — Zuhaira Ilyana, Apr 14 '17 at 09:12
It's unclear what you are asking. You should give more information if you can't put into words at least give a sample input and desired output — Emad, Apr 14 '17 at 09:15
Are numbers single digit, or are they any possible number? For example, imput is [1, 2, 3] and combinations are 123, 231, ... etc. Or the imput is [12, 34, 1] and combinations are [1, 34, 12], ... etc? — Zoran Basic, Apr 14 '17 at 09:16
So if you provide [1,2,3,4], do you want 1*2*3*4, or 4*3 (since that's the biggest product?) — ProgrammingLlama, Apr 14 '17 at 09:19
I see that all the numbers on each line add up to the target. — vyrp, Apr 14 '17 at 11:03
@vyrp I wan the line that have only 3 rows that will be display as the output. As u can seen that several line have 5 rows , 4 rows and 3 rows. So I just want the 3 rows only. — Zuhaira Ilyana, Apr 15 '17 at 03:00

vyrp · Accepted Answer · 2017-04-15T10:06:24.947

From the comments in the question and other answers, it seems to me that the OP already knows how to calculate all the combinations whose sum is a target number (that's probably what the Solver in the question does). What I think he wants is to get the combination with the least amount of numbers.

I have a couple of solutions, since I'm not really sure what you want:

1) If you want all the combinations with the least of amount of numbers, do this:

public static void Main()
{
    // Here I have hard-coded all the combinations,
    // but in real life you would calculate them.
    // Probably using your `Solver` or any of the other answers in this page.
    var combinations = new List<List<decimal>>{
        new List<decimal>{ 1, 2, 3, 4, 5 },
        new List<decimal>{ 1, 2, 5, 7 },
        new List<decimal>{ 1, 3, 4, 7 },
        new List<decimal>{ 1, 3, 5, 6 },
        new List<decimal>{ 2, 3, 4, 6 },
        new List<decimal>{ 2, 6, 7 },
        new List<decimal>{ 3, 5, 7 },
        new List<decimal>{ 4, 5, 6 }
    };

    // Filter the list above to keep only the lists
    // that have the least amount of numbers.
    var filteredCombinations = LeastNumbers(combinations);

    foreach (var combination in filteredCombinations)
    {
        Console.WriteLine(string.Join("\t", combination));
    }
}

public static List<List<decimal>> LeastNumbers(List<List<decimal>> combinations)
{
    // First get the count for each combination, then get the minimum of those.
    int smallestLength = combinations.Select(l => l.Count).Min();

    // Second, only keep those combinations which have a count equals to the value calculated above.
    return combinations.Where(l => l.Count == smallestLength).ToList();
}

Output:

2    6    7
3    5    7
4    5    6

2) If you only want one of the combinations with the least amount of numbers, do this instead:

public static void Main()
{
    // Here I have hard-coded all the combinations,
    // but in real life you would calculate them.
    // Probably using your `Solver` or any of the answers in this page.
    var combinations = new List<List<decimal>>{
        new List<decimal>{ 1, 2, 3, 4, 5 },
        new List<decimal>{ 1, 2, 5, 7 },
        new List<decimal>{ 1, 3, 4, 7 },
        new List<decimal>{ 1, 3, 5, 6 },
        new List<decimal>{ 2, 3, 4, 6 },
        new List<decimal>{ 2, 6, 7 },
        new List<decimal>{ 3, 5, 7 },
        new List<decimal>{ 4, 5, 6 }
    };

    // Filter the list above to keep only the first list
    // that has the least amount of numbers.
    var filteredCombination = LeastNumbers(combinations);

    Console.WriteLine(string.Join("\t", filteredCombination));
}

public static List<decimal> LeastNumbers(List<List<decimal>> combinations)
{
    // First get the count for each combination,
    // then get the minimum of those.
    int smallestLength = combinations.Select(l => l.Count).Min();

    // Second, get only one of the combinations that have a count
    // equals to the value calculated above.
    return combinations.First(l => l.Count == smallestLength);
}

Output:

2    6    7

3) The OP also mentioned a max value of 3. So, if you know that number before-hand, you can do this:

public static void Main()
{
    // Here I have hard-coded all the combinations,
    // but in real life you would calculate them.
    // Probably using your `Solver` or any of the answers in this page.
    var combinations = new List<List<decimal>>{
        new List<decimal>{ 1, 2, 3, 4, 5 },
        new List<decimal>{ 1, 2, 5, 7 },
        new List<decimal>{ 1, 3, 4, 7 },
        new List<decimal>{ 1, 3, 5, 6 },
        new List<decimal>{ 2, 3, 4, 6 },
        new List<decimal>{ 2, 6, 7 },
        new List<decimal>{ 3, 5, 7 },
        new List<decimal>{ 4, 5, 6 }
    };

    // This must be known before hand.
    // That's why I think my first solution is more usefull.
    int max = 3;

    // Filter the list above to keep only the lists
    // that have a count less or equal to a predetermined maximum.
    var filteredCombinations = FilterByMaxLength(combinations, max);

    foreach (var combination in filteredCombinations)
    {
        Console.WriteLine(string.Join("\t", combination));
    }
}

public static List<List<decimal>> FilterByMaxLength(List<List<decimal>> combinations, int max)
{
    return combinations.Where(l => l.Count <= max).ToList();
}

2    6    7
3    5    7
4    5    6

Note: In a real scenario, you would also want to do some checking in those functions, like checking for null or empty lists.

I'll try it. Thank you btw. – Zuhaira Ilyana Apr 16 '17 at 01:15 — Zuhaira Ilyana, Apr 16 '17 at 01:15

Leze · Answer 2 · 2017-04-14T12:48:40.290

Hard to find what you're trying to do, is something like this

List<string> numbers = new List<string>(){"1","2","3","4","5"};
List<string> possibleCombination = GetCombination(numbers, new List<string>(), "");
Console.Write(string.Join(", ",possibleCombination.Distinct().OrderBy(itm => itm)));

The method

static List<string> GetCombination(List<string> list, List<string> combinations, string sumNum, bool addNumberToResult = false)
    {
        if (list.Count == 0) {
            return combinations;
        }

        string tmp;

        for (int i = 0; i <= list.Count - 1; i++) {
            tmp = string.Concat(sumNum , list[i]);
            if(addNumberToResult){
                combinations.Add(tmp);
            }
            List<string> tmp_list = new List<string>(list);
            tmp_list.RemoveAt(i);
            GetCombination(tmp_list,combinations,tmp, true);
        }

        return combinations;
    }

C# Fiddle can help you?

thanks for the answer. but I want the output that return 3 numbers or less only. — Zuhaira Ilyana, Apr 15 '17 at 03:10

score 0 · Answer 3 · edited May 23 '17 at 11:54

Here is my try, you can tweak this depending on what you want:

using System.Collections.Generic;
using System.Linq;        
private static void GetMaxPermutation(int max)
        {
            var numbers = new[] { 1, 2, 4, 6, 7 };
            var results = new List<IEnumerable<int>>();
            for (int i = 1; i <= numbers.Length; i++)
            {
                results.AddRange(GetPermutations(numbers, i));
            }
            Console.WriteLine("Result: " + string.Join(" ", results.Select(x => new { Target = x, Sum = x.Sum() }).Where(x => x.Sum <= max).OrderByDescending(x => x.Sum).FirstOrDefault().Target));
        }

    private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count)
    {
        int i = 0;
        foreach (var item in items)
        {
            if (count == 1)
                yield return new T[] { item };
            else
            {
                foreach (var result in GetPermutations(items.Skip(i + 1), count - 1))
                    yield return new T[] { item }.Concat(result);
            }

            ++i;
        }
    }

I got this permutations method from here

c# How to set the maximum number when do the find all possible combinations of numbers to reach a given sum

3 Answers3