Linq Expression - Extract smallest Integer Array sizes only

Question

I have a list of integers which will only contain 4 numbers as shown, I need to write a Linq expression which extracts a list of integer Arrays containing only numbers whose addition is equal to "total", sounds simple but here's the tricky part I only want integer Arrays with the smallest count, so if total = 4, then I'd want int[]{4} but I would want int[]{2,2} or int[]{1,3} etc, if total was 5 then I'd want int[]{1,4} , int[]{4,1} , int[]{2,3} , int[]{3,2}, perhaps this could be done with a whole pile of if statements but I'm hoping there's an elegent linq expression out there.

var total = 5;
var numList = new List<int>() { 1, 2, 3, 4 };

This sounds a lot like a homework question... Can you show your attempt? It is an interesting problem though. — BradleyDotNET, May 28 '14 at 21:14
The only thing I can do so far is extract all integer arrays were four number add up to "total" so if total was 8, then I'd have int[]{2,2,1,3} as one result, but this has four numbers were it could have been done with just int[] {4,4} — chillydk147, May 28 '14 at 21:18
Are you asking for _all possible permutations_ of `numList` that can give you that total? Or are you given an initial set of arrays/permutations to check? — Chris Sinclair, May 28 '14 at 21:19
And on second read, not only basic permutations but _order permutations_ as well? That is, for the above `numList` for total `7`, both `{3, 4}` _and_ `{4, 3}` would be returned? But not only that: `{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}`? — Chris Sinclair, May 28 '14 at 21:22
@chillydk147: Ahh, my mistake, right, smallest. But if `3` wasn't available, you'd have that many combinations to return? — Chris Sinclair, May 28 '14 at 21:24
@Chris Array will always be {1,2,3,4} and total will never exceed 16 — chillydk147, May 28 '14 at 21:25
@chillydk147: Ahh. Well, for the sake of learning/understanding, I'd suggest trying to write it out with a more verbose algorithm and _then_ trying to compose it to LINQ queries. As it stands, you have a couple _different_ tasks here: first you must attempt to find _combinations_ of values that equal your sum ascending in number of picks (that is, start by all possible ways to pick 1, check sums, then if none equal your total, all possible ways to pick 2, and so on), _then_ find all possible order permutations of those picks. _And_ finally, do so for all combination "ties" ({2,2} & {3,1}) — Chris Sinclair, May 28 '14 at 21:29
@MarcinJuraszek: Obviously but if there's a linq solution then why not use it — chillydk147, May 28 '14 at 21:31
@chillydk147: cont.: Once you break down your problem to its constituent steps (combinations, summation, & permutations) _and understand how those work_, then you can try rewriting them in more elegant ways or applying LINQ to those individual parts. _Then_ you might be able to write a large LINQ query combining them. Better to get it _working_ first (with automated tests) _then_ try to rewrite them elegantly to make sure your rewritten LINQ queries are _correct_ against your tests. — Chris Sinclair, May 28 '14 at 21:31
@chillydk147 why are you so set on using LINQ for this solution? What benefits do you hope to get from it? — Nick Udell, May 28 '14 at 21:32
@Nick: I'm only learning linq since yesterday so just want to play around with it — chillydk147, May 28 '14 at 21:34
possible duplicate of [Getting all possible sums that add up to a given number](http://stackoverflow.com/questions/7331093/getting-all-possible-sums-that-add-up-to-a-given-number) — Codeman, May 28 '14 at 22:01

score 0 · Answer 1 · answered Jun 05 '14 at 09:39

0

You have to start out with a fairly complicated bit of code to produce all of the combinations of the source array. Like this:

public IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> source)
{
    if (!source.Any())
    {
        return Enumerable.Empty<IEnumerable<T>>();
    }
    else if (!source.Skip(1).Any())
    {
        return new [] { source, source.Take(0) };
    }
    else
    {
        return Combinations(source.Skip(1))
            .SelectMany(xs => new [] { source.Take(1).Concat(xs), xs });
    }
}

Now the rest is easy. Just do this:

var query =
(
    from xs in Combinations(new [] { 1, 2, 3, 4, })
    where xs.Sum() == 5
    orderby xs.Count()
    group xs by xs.Count()
)
    .Take(1)
    .SelectMany(xs => xs);

I get the follow result as expected:

result

answered Jun 05 '14 at 09:39

Enigmativity

113,464
11
89
172

If I make a set, say `Enumerable.Range(1, 1024)`, and I want to find the first combination that sums to `1`, your solution is going to take a very long time to find that. – Jodrell Jun 05 '14 at 11:08
@Jodrell - Yes, I agree. It would take around 10^300 seconds to compute. Not very practical. But for small quantities of numbers this works. – Enigmativity Jun 05 '14 at 12:24
of, course, im my silly test, you could prefilter the list with `numList.Where(n => n <= total)`. – Jodrell Jun 05 '14 at 14:47
@Jodrell - Yes, you actually made me think that you could push the filter into the list gen to determine when to stop further processing because either you've gone over the required value or if there are insufficient values in the remaining list to make it viable to continue. The trick would be making sure those checks are efficient - or at least more efficient than blindly moving forward. – Enigmativity Jun 05 '14 at 23:44

score 0 · Answer 2 · answered Jun 05 '14 at 11:05

okay, here is a function

/// <summary>
/// Gets integer combinations between 0 and an exclusive upper bound.
/// </summary>
/// <param name="l">The length of the combination.</param>
/// <param name="n">The exclusive upper bound.</param>
/// <returns>
/// All combinations of the specified length in the specified range.
/// </returns>
public static IEnumerable<IEnumerable<int>> Combinations(int l, int n)
{
    var result = new int[l];
    var stack = new Stack<int>();
    stack.Push(0);

    while (stack.Count > 0)
    {
        var index = stack.Count - 1;
        var value = stack.Pop();

        while (value < n)
        {
            result[index++] = value++;
            stack.Push(value);
            if (index == 1)
            {
                yield return result;
                break;
            }
        }
    }
}

You can use that in an extension method like this.

public static IEnumerable<IEnumerable<T>> CombinationsIncreasingLength<T>(
        this IEnumerable<T> source)
{
    var sourceList = source.ToList();

    if (sourceList.Count < 2)
    {
        return new[] { sourceList };
    }

    return
        Enumerable.Range(1, sourceList.Count)
            .SelectMany(l => Combinations(l, sourceList.Count)
                .Select(indices => indices.Select(i => sourceList[i])));
}

That will give you all the combinations of the source in increasing length.

So to find the shortest combination that sum exactly to value, you can do.

numList.CombinationsIncreasingLength().First(c => c.Sum() == total);

Linq Expression - Extract smallest Integer Array sizes only

2 Answers2