Linq query to get all numbers (positive and negative) up to N that sum up to number K-CodePudding

I have a specific assignment to make a function that only uses LINQ, this is what makes it challenging for me. The problem is something like:

Generate all expressions of plus and minus ( -) of N numbers that sum up to K.

Example if I have N = 3, K = 0. I should have at some point 8 combinations of numbers with plus and minus (2 to the power of n combinations), and with some Where clause I should only extract those who sum up to 0 (which is K). So the result should be something like:

-1 -2 3 = 0;

1 2 -3 = 0;

Again, I can only use LINQ queries, nothing else, and I can't wrap my head around this problem. Can anyone help?

This is the function that I came up with but it's wrong as there are multiple results that are the same, but for very small inputs it somehow works.

    public static IEnumerable<IEnumerable<int>> AllCombinations(int n, int k)
    {
        if (n < 1)
        {
            throw new ArgumentException("N should be bigger than 0");
        }

        int[] baseValues = { -1, 1 };
        int rows = (int)Math.Pow(2, n);

        return Enumerable.Range(0, rows).Select(i => Enumerable.Range(1, n).Select(j => baseValues[i / (rows / (j * 2)) % 2] * j))
        .Where(s => s.Sum() == k);
    }

CodePudding user response：

The question is a bit unclear, but perhaps something of the form:

        var q =
        from n1 in Enumerable.Range(-n, 1 2*n)
        from n2 in Enumerable.Range(-n, 1 2*n)
        from n3 in Enumerable.Range(-n, 1 2*n)
        where n1   n2   n3 == k
        where n1 <= n2
        where n2 <= n3 
        select new { n1, n2, n3 };

CodePudding user response：

Here is a hackish solution, using only brute force. I'm sure a most elegant one can be found. It will also fail to produce results for more than 30 numbers.

Enumerable
    .Range(0, (int)Math.Pow(2, N))
    .Select(i => Convert.ToString(~i, 2)
        .Reverse()
        .Take(N)
        .Select((c, i) => c == '1' ? i   1 : -(i   1))
        .ToList())
    .Where(l => l.Sum() == K)
    .ToList();

Some explanations:

As you pointed out, for N numbers, there are 2^N combinations of sums with or -. So the first step is to build these 2^N combinations.

Enumerable
    .Range(0, (int)Math.Pow(2, N))

constructs the first 2^N numbers. Lets consider in this example that N = 10.

.Select(i => Convert.ToString(~i, 2)

Transforms each number to its binary string representation, but inverted (0 is replaced by 1, and 1 is replaced by 0). The purpose of the inversion is to get all the 32 digits of the number, otherwise the number 2, i.e. 10 in binary would be represented by the string "10". And we want a string as long as N. i.e. "0000000010". With that trick, instead of "01", we get "1111111111111111111111111111101".

That string is then considered as a sequence of characters.

.Reverse()

That sequence is reversed: "1011111111111111111111111111111",

.Take(N)

And we take only the first N characters: "1011111111".

.Select((c, i) => c == '1' ? i   1 : -(i   1))
.ToList())

Then we project each character to an number, which is the index 1, with a sign depending on the character itself: if equal to '1' plus, otherwise -. Which gives: 1, -2, 3, 4, 5, 6, 7, 8, 9, 10 in the example used until now.

.Where(l => l.Sum() == K)
.ToList();

From there we have constructed all possible sequences, so we can sum these and filter the ones for which the sum equals our target.

Of course you could add a check: if |K| > (N^2 N)/2, there is no need to calculate, there won't be no matches...

As a query you try by copy/paste in Linqpad:

void Main()
{
    Utils.Calculate(10, 1)
        .Select(e => new 
        {
            Sum = e.Sum(),
            Elements = e
        })
        .Dump();
}

// You can define other methods, fields, classes and namespaces here
public static class Utils
{
    public static List<List<int>> Calculate(int N, int K)
    {
        // Enumerable.Range will throw ArgumentOutOfRangeException 
        // if N <= 0 || N > 30
        
        return Enumerable
            .Range(0, (int)Math.Pow(2, N))
            .Select(i => Convert.ToString(~i, 2)
                .Reverse()
                .Take(N)
                .Select((c, i) => c == '1' ? i   1 : -(i   1))
                .ToList())
            .Where(l => l.Sum() == K)
            .ToList();
    }
}

EDIT The same logic could also be written as:

Enumerable.Range(1, (int)Math.Pow(2, N))
    .Select(i => int.MaxValue - i   1)
    .Select(i => Convert.ToString(i, 2)
        .Skip(31-N)
        .Select((c, i) => c == '1' ? i   1 : -(i   1))
        .ToList())
    .Where(l => l.Sum() == K)
    .ToList()

To order of the lists will be different from the first method, which doesn't matter for the result.