Linq 查询获取所有数字（正数和负数）最多 N 个，总和为数字 K

Question

我有一个特定的任务是创建一个只使用 LINQ 的函数 ，这就是它对我来说具有挑战性的原因。问题是这样的：

生成N个数的所有正负(+-)表达式，总和为K

例如，如果我有 N = 3，K = 0。我应该在某个时候有 8 种数字组合，包括加号和减号（2 的 n 次方组合），以及一些我应该只提取的 Where 子句那些总和为 0（即 K）的人。所以结果应该是这样的：

-1 -2 +3 = 0;

+1 +2 -3 = 0;

同样，我只能使用 LINQ 查询，不能使用其他任何东西，而且我无法解决这个问题。有人可以帮忙吗？

Answer 1

这是一个仅使用蛮力的骇人听闻的解决方案。我相信可以找到一个最优雅的。对于超过 30 个数字，它也将无法生成结果。

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();

一些解释：

正如您所指出的，对于 N 个数字，有 2^N 种和+或-的组合。所以第一步是构建这些 2^N 组合。

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

构造前2^N个数。让我们在这个例子中考虑 N = 10.

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

将每个数字转换为其二进制字符串表示形式，但取反（0 替换为 1，1 替换为 0）。反转的目的是获取数字的所有 32 位数字，否则数字 2，即二进制中的 10 将由字符串“10”表示。我们想要一个与 N 一样长的字符串，即“0000000010”。通过这个技巧，我们得到的不是“01”，而是“1111111111111111111111111111101”。

然后该字符串被视为字符序列。

.Reverse()

该序列是相反的：“1011111111111111111111111111111”，

.Take(N)

我们只取前 N 个字符：“1011111111”。

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

然后我们将每个字符投影到一个数字，即索引+1，符号取决于字符本身：如果等于'1'加，否则-。这给出了： 1, -2, 3, 4, 5, 6, 7, 8, 9, 10 在到目前为止使用的示例中。

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

从那里我们构建了所有可能的序列，因此我们可以对这些序列求和并过滤出总和等于我们的目标的序列。

当然你可以添加一个检查：if |K| > (N^2 + N)/2，不用计算，不会没有匹配...

作为您在 Linqpad 中通过 copy/paste 尝试的查询：

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();
    }
}

编辑同样的逻辑也可以写成：

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()

列表的顺序将与第一种方法不同，这与结果无关。

Answer 2

这里有一个相当简单的方法：

int n = 3;
int k = 0;

IEnumerable<int[]> query =
    from i in Enumerable.Range(0, 1 << n)
    let b = Convert.ToString(i, 2).PadLeft(n, '0')
    let r = Enumerable.Range(1, n)
    let d = r.Zip(b, (x, y) => y == '0' ? x : -x).ToArray()
    let s = d.Sum()
    where s == k
    select d;

运行给了我：

1, 2, -3
-1, -2, 3

并且，例如，使用 n = 9 和 k = 33 我得到：

1, 2, 3, 4, 5, -6, 7, 8, 9
1, -2, 3, -4, 5, 6, 7, 8, 9
-1, 2, 3, 4, -5, 6, 7, 8, 9
-1, -2, -3, 4, 5, 6, 7, 8, 9

这样可以避免创建字符串：

IEnumerable<bool> GetBits(int q, int v) =>
    q == 0
    ? Enumerable.Empty<bool>()
    : GetBits(q - 1, v >> 1).StartWith((v & 1) == 1);

int n = 13;
int k = 75;

IEnumerable<IEnumerable<int>> query =
    from i in Enumerable.Range(0, 1 << n)
    let bs = GetBits(n, i)
    let rs = Enumerable.Range(1, n)
    let ds = rs.Zip(bs, (x, y) => y ? x : -x)
    let s = ds.Sum()
    where s == k
    select ds;

Answer 3

所以问题是关于决定从 1 到 N 的每个整数是否应该相加或相减？

public static IEnumerable<IEnumerable<int>> AllCombinations(int n, int k)
    => Enumerable.Range(0, 1 << n)
        .Select(i =>
            Enumerable.Range(0, n)
                .Select(j => (i & 1 << j) == 0 ? j + 1 : -j - 1)
        )
        .Where(r => r.Sum() == k);

Answer 4

感谢任何试图提供帮助的人，不幸的是，所有解决方案对于这个问题都太复杂了，所以我设法找到了自己的解决方案，它更简单一些，但你的解决方案引导我朝着正确的方向前进。

IEnumerable<string> seed = new[] { "" };

var x = Enumerable.Range(0, n).Aggregate(seed, (a, _) => a.
        SelectMany(s => new[] { s + "+", s + "-" }));

return x.Select((a) => a.Select((a, b) => a == '+' ? b + 1 : (b + 1) * -1))
.Where(r => r.Sum() == k);

Answer 5

根据 OP 的回答，这是一个替代方案，它使用 int[] 建立候选人名单。

int n = 26;
int k = 8;

var sw = Stopwatch.StartNew();

IEnumerable<int[]> seed = new[] { new int[] { } };
var xss =
    Enumerable
        .Range(1, n)
        .Aggregate(
            seed,
            (a, i) => a.SelectMany(s => new[]
            {
                s.Append(i).ToArray(),
                s.Append(-i).ToArray(),
            }))
        .Where(xs => xs.Sum() == k)
        .ToArray();

sw.Stop();
sw.ElapsedMilliseconds.Dump();

这比 OP 的字符串构建方法更快。

Linq 查询获取所有数字（正数和负数）最多 N 个，总和为数字 K

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

c#

linq

combinations