我有一個特定的任務來制作一個只使用 LINQ的函式，這對我來說是一個挑戰。問題是這樣的：
生成總和為 K 的 N 個數字的所有加減 ( -) 運算式。
例如，如果我有 N = 3，K = 0。我應該在某個時候有 8 種數字的正負組合（2 的 n 次組合），并且使用一些 Where 子句，我應該只提取那些總和為0（即 K）。所以結果應該是這樣的：
-1 -2 3 = 0;
1 2 -3 = 0；
同樣，我只能使用 LINQ 查詢，沒有別的，我無法解決這個問題。任何人都可以幫忙嗎？
這是我想出的函式，但它是錯誤的，因為有多個相同的結果，但對于非常小的輸入，它以某種方式起作用。
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);
}
uj5u.com熱心網友回復：
所以問題是關于決定是否應該添加或減去從 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);
uj5u.com熱心網友回復：
這是一個駭人聽聞的解決方案，僅使用蠻力。我相信可以找到一個最優雅的。它也無法生成超過 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”，而是“11111111111111111111111111111101”。
然后將該字串視為字符序列。
.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 中復制/粘貼來嘗試：
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()
串列的順序將與第一種方法不同，這對結果無關緊要。
uj5u.com熱心網友回復：
這是一個相當簡單的方法：
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;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/364967.html
上一篇：C#LINQ從字串陣列中選擇元素
下一篇：在C#中動態查詢Mongo集合