没有重复的单词组合
我有10个字。 如何获得5个单词的所有可能组合(n=10, k=5)
。 订单无关紧要 。
例如: "A", "B", "C", if k=2 (n=3 in this case)
,它将需要AB,BC和AC。 也许你知道一些有用的代码或例子。
PS对不起,如果我不对,因为我不太懂英语。
你要做的是获得一个集合的所有排列。
- 列表的唯一排列
- 来自一组n算法的k个对象的排列
这是代码片段:
static void Main(string[] args) { var list = new List { "a", "b", "c", "d", "e" }; var result = GetPermutations(list, 3); foreach (var perm in result) { foreach (var c in perm) { Console.Write(c + " "); } Console.WriteLine(); } Console.ReadKey(); } static IEnumerable> GetPermutations(IEnumerable items, int count) { int i = 0; foreach (var item in items) { if (count == 1) yield return new T[] { item }; else { foreach (var result in GetPermutations(items.Skip(i + 1), count - 1)) yield return new T[] { item }.Concat(result); } ++i; } }
输出:
abcabdabeacdaceadebcd bcebdecde
那么更实用的解决方案呢?
var list = new List { "a", "b", "c", "d", "e" }; GetAllCombinations(list).OrderBy(_ => _).ToList().ForEach(Console.WriteLine); static IEnumerable GetAllCombinations(IEnumerable list) { return list.SelectMany(mainItem => list.Where(otherItem => !otherItem.Equals(mainItem)) .Select(otherItem => mainItem + otherItem)); }
输出继电器:
ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed
这是我放在一起的东西:
static class LinqExtensions { public static IEnumerable> CombinationsWithoutRepetition( this IEnumerable items, int ofLength) { return (ofLength == 1) ? items.Select(item => new[] { item }) : items.SelectMany((item, i) => items.Skip(i + 1) .CombinationsWithoutRepetition(ofLength - 1) .Select(result => new T[] { item }.Concat(result))); } public static IEnumerable> CombinationsWithoutRepetition ( this IEnumerable items, int ofLength, int upToLength) { return Enumerable.Range(ofLength, Math.Max(0, upToLength - ofLength + 1)) .SelectMany(len => items.CombinationsWithoutRepetition(ofLength: len)); } }
…
foreach (var c in new[] {"a","b","c","d"}.CombinationsWithoutRepetition(ofLength: 2, upToLength: 4)) { Console.WriteLine(string.Join(',', c)); }
生产:
a,b a,c a,d b,c b,d c,d a,b,c a,b,d a,c,d b,c,d a,b,c,d
请注意,这是简洁但效率低下的,不应该用于大型集合或内部循环。 值得注意的是,短数组被重新创建多次并且可以被记忆,并且IEnumerable
将被多次迭代,如果不小心,这可能导致意外的工作。
此外,如果输入包含重复项,那么输出也将是。 首先使用.Distinct().ToArray()
,或者使用另一个包含相等性检查的解决方案,并且可能IEqualityComparer
用于通用性。