C# Linq 中的组合生成器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/774457/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Combination Generator in Linq
提问by CasperT
Is it possible to create some Linq that generates a List containing all possible combinations of a series of numbers??
是否可以创建一些 Linq 来生成包含一系列数字的所有可能组合的列表？
If you enter "21" it would generate a list with the elements:
如果您输入“21”，它将生成一个包含以下元素的列表：
list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"
(Not nessesarily in that order)
（不一定按这个顺序）
I understand you can use range to do things like:
我知道您可以使用 range 来执行以下操作：
List<char> letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations
Which generates the alphabet from a-z. But I can not seem to transfer this knowledge to make a combination generator
它从 az 生成字母表。但我似乎无法将这些知识转移到组合生成器上
I have been able to figure it out with the following code, but it seems way too bulky and I am sure it can be done with a few lines. It really does feel like a bad solution I have made.
我已经能够用下面的代码弄清楚它，但它看起来太笨重了，我相信它可以用几行来完成。我确实觉得这是一个糟糕的解决方案。
Imagine I have called GetAllCombinations("4321")if it helps
想象一下，GetAllCombinations("4321")如果有帮助，我会打电话
public static String[] GetAllCombinations(String s)
{
var combinations = new string[PossibleCombinations(s.Length)];
int n = PossibleCombinations(s.Length - 1);
for (int i = 0; i < s.Length; i++)
{
String sub;
String[] subs;
if (i == 0)
{
sub = s.Substring(1); //Get the first number
}
else if (i == s.Length - 1)
{
sub = s.Substring(0, s.Length - 1);
}
else
{
sub = s.Substring(0, i) + s.Substring(i + 1);
}
subs = GetAllCombinations(sub);
for (int j = 0; j < subs.Length; j++)
{
combinations[i * n + j] = s[i] + subs[j];
}
}
return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
采纳答案by Josh G
For what it's worth, try something like this:
对于它的价值，尝试这样的事情：
public static IEnumerable<string> GetPermutations(string s)
{
if (s.Length > 1)
return from ch in s
from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
select string.Format("{0}{1}", ch, permutation);
else
return new string[] { s };
}
回答by Adam Robinson
What you're looking for are actually permutations. In short, permutations means that order is relevant (ie, 12 is different from 21) whereas a combination means order is irrelevant (12 and 21 are equivalent). For more information see Wikipedia.
您正在寻找的实际上是排列。简而言之，排列意味着顺序是相关的（即，12 与 21 不同），而组合意味着顺序是不相关的（12 和 21 是等效的）。有关更多信息，请参阅维基百科。
See this thread.
看到这个线程。
As for doing is in pure LINQ, that sounds like using LINQ for the sake of using LINQ.
至于做纯LINQ，听起来像是为了使用LINQ而使用LINQ。
回答by Marc Wittke
For the record: Josh's answer the generic way:
作为记录：乔希的回答是通用的方式：
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
if (items.Count() > 1) {
return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
(item, permutation) => new[] { item }.Concat(permutation));
} else {
return new[] {items};
}
}
回答by Yongkee Cho
Here is my Permutation and Combination function using Linq
这是我使用 Linq 的排列和组合函数
public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
if (source == null)
throw new ArgumentNullException("source");
yield return item;
foreach (var element in source)
yield return element;
}
public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
if (source == null)
throw new ArgumentNullException("source");
var list = source.ToList();
if (list.Count > 1)
return from s in list
from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
select p.Prepend(s);
return new[] { list };
}
public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
if (source == null)
throw new ArgumentNullException("source");
var list = source.ToList();
if (k > list.Count)
throw new ArgumentOutOfRangeException("k");
if (k == 0)
yield return Enumerable.Empty<TSource>();
foreach (var l in list)
foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
yield return c.Prepend(l);
}
For the DNA alphabet 'A', 'C', 'G', 'T':
对于 DNA 字母“A”、“C”、“G”、“T”：
var dna = new[] {'A', 'C', 'G', 'T'};
foreach (var p in dna.Permutate())
Console.WriteLine(String.Concat(p));
gives
给
ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA
and the combinations (k = 2) of DNA alphabet
和 DNA 字母的组合 (k = 2)
foreach (var c in dna.Combinate(2))
Console.WriteLine(String.Concat(c));
are
是
AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT
回答by Mark Feldman
As others have pointed out the solutions on this page will generate duplicates if any of the elements are the same. The Distinct() extension will remove them, but it's not very scalable as it will usually result in the entire search tree being traversed anyway. You'll trim the search space considerably by invoking it during traversal:
正如其他人所指出的，如果任何元素相同，此页面上的解决方案将生成重复项。Distinct() 扩展将删除它们，但它的可扩展性不是很好，因为它通常会导致遍历整个搜索树。您将通过在遍历期间调用它来显着修剪搜索空间：
private static IEnumerable<string> Permute(string str)
{
if (str.Length == 0)
yield return "";
else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
foreach (var p in Permute(str.Remove(index, 1)))
yield return str[index] + p;
}
For the example string "bananabana" this results in 8,294 nodes being visited, as opposed to the 9,864,101 visited when you don't do traversal culling.
对于示例字符串“bananabana”，这会导致访问 8,294 个节点，而不是在不进行遍历剔除时访问的 9,864,101 个节点。
回答by Robear
You can use this Permute LINQ extension:
您可以使用这个 Permute LINQ 扩展：
foreach (var value in Enumerable.Range(1,3).Permute())
Console.WriteLine(String.Join(",", value));
Which results in this:
结果如下：
1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...
You can optionally specify the # of permutations
您可以选择指定排列数
foreach (var value in Enumerable.Range(1,2).Permute(4))
Console.WriteLine(String.Join(",", value));
Results:
结果：
1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2
Extension Class to add:
要添加的扩展类：
public static class IEnumberableExtensions
{
public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}
