Как найти все возможные комбинации формы ± 1 ± 2 ± 3 ± ... ± n = k с помощью LINQ?

Question

Мне очень сложно найти простое решение этой проблемы с использованием LINQ в C#:

Для двух заданных чисел n и k найдите все возможные комбинации формы ± 1 ± 2 ± 3 ± ... ± n = k.

Например, для n = 5 и k = 3 результат будет "-1+2+3+4-5 = 3", "-1+2+3+4-5 = 3"

public static void Main()
{
    int firstNNumbers = Convert.ToInt32(Console.ReadLine());
    int numberOfOperations = firstNNumbers - 1;
    int targetSum = Convert.ToInt32(Console.ReadLine());
    char[] set = { '+', '-' };
    bool hasSolution = false;
    GetAllOperatorCombinations(set, numberOfOperations, targetSum, ref hasSolution);
    if (hasSolution)
    {
        return;
    }
    Console.WriteLine("N/A");
}
public static int CheckIfGoodAndPrint(string prefix, int targetSum, ref bool hasSolution)
{
    const int Number = 2;
    int thisSum = 1;
    if (prefix == null)
    {
        return -1;
    }
    for (int i = 0; i < prefix.Length; i++)
    {
        if (prefix[i] == '-')
        {
            thisSum -= i + Number;
        }
        else
        {
            thisSum += i + Number;
        }
    }
    if (thisSum != targetSum)
    {
        return -1;
    }
    PrinEquation(prefix, targetSum);
    hasSolution = true;
    return 1;
}
static void GetAllOperatorCombinations(char[] set, int k, int targetSum, ref bool hasSolution)
{
    int n = set.Length;
    GetAllOperatorCombinations(set, "", n, k, targetSum, ref hasSolution);
}
static void GetAllOperatorCombinations(char[] set, string prefix, int n, int k, int targetSum, ref bool hasSolution)
{
    if (k == 0)
    {
        int test = CheckIfGoodAndPrint(prefix, targetSum, ref hasSolution);
        return;
    }
    for (int i = 0; i < n; ++i)
    {
        string newPrefix = prefix + set[i];
        GetAllOperatorCombinations(set, newPrefix, n, k - 1, targetSum, ref hasSolution);
    }
}
private static void PrinEquation(string prefix, int targetSum)
{
    string equation = "";
    for (int i = 1; i <= prefix.Length; i++)
    {
        equation += i + " " + prefix[i - 1] + " ";
        if (i == prefix.Length)
        {
            equation += (i + 1) + " = " + targetSum;
        }
    }
    Console.WriteLine(equation);
}

Это код, который работает во всех случаях, но я знаю, что с linq его можно сделать намного короче.

Answer 1

Вот возможное итеративное решение:

using System;
using System.Linq;

public class Program
{
    public static void Main()
    {
        const int N = 5, K = 3;

        // 1 represents +, 0 represents -
        var results = Enumerable.Range(0, 1 << N)
            .Select(bits =>
            {
                var permutation = Enumerable.Range(0, N)
                    .Select(n => (bits & (1 << n)) != 0 ? (n + 1) : -(n + 1))
                    .ToList();

                var sum = permutation.Sum();
                var str = string.Join(" + ", permutation);

                return new {sum, str};
            })
            .Where(intermediate => intermediate.sum == K)
            .Select(intermediate => $"{intermediate.str} = {K}");

        Console.WriteLine(string.Join("\n", results));
    }
}

Это использует тот факт, что можно перебирать двоичное представление всех целых чисел от 0 до 2 ^ N - 1, чтобы сгенерировать все возможные перестановки либо +, либо - (в данном случае, представленных битами 1 и 0 соответственно.)

Это, по сути, превращает эту проблему в один l oop.

Почему это работает, довольно интуитивно понятно; Проще говоря, существует 2 ^ N возможных последовательностей длины N двухзначного типа, а также есть 2 ^ N целых чисел между 0 и 2 ^ N - 1 (очевидно), поэтому каждая возможность должна встречаться точно один раз.

Для ваших входных значений N = 5 и K = 3 это дает ( ideone )

-1 + 2 + 3 + 4 + -5 = 3
1 + -2 + 3 + -4 + 5 = 3
-1 + -2 + -3 + 4 + 5 = 3

Answer 2

public static IEnumerable<string> CombinationOfSigns(this int n,int k)
        {
            IEnumerable<string> signs = new string[] {""};
            return Enumerable.Range(0, n)
                .Aggregate(signs,(e,y) => e
                .SelectMany(x => new string[] { x + "-", x + "+" }))
                .Where(combination => Enumerable.Range(0, n)
                .Aggregate(0, (sum, number)=> combination[number] == '+' ? sum + (number + 1) : sum - (number + 1)) == k);
        }

Это то, что я в итоге придумал.