如何使用LINQ从一组数字中找到n项的所有组合
本文关键字:组合 数字 LINQ 何使用 一组 | 更新日期: 2023-09-27 18:19:08
我正在尝试编写一个算法,从一组数字中选择n个值的所有组合。
例如,给定集合:1, 2, 3, 7, 8, 9
集合中2个值的所有组合为:
(1、2),(1、3)、(7)、(8)、(9)、(2、3)、(7)、(8)、(9)、(7)、(8)、(9)、(7、8),(7、9),(8、9)
和3是:
(1、2、3),(1、2、7),(1、2、8),(1、2、9),(1、3、7),(1、3、8),(1、3、9),(1、7、8),(1、7、9),(1、8、9),(2、3、7),(2、3、8),(2、3、9),(2、7、8),(2、7、9),(2,8,9),(3、7、8),(3、7、9),(3、8、9),(7,8,9)
等!
我目前正在使用方法来产生2、3和4值的组合返回集,但在我看来,这可以在LINQ查询中进行概括。
用法:
var results = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.DifferentCombinations(3);
代码:
public static class Ex
{
public static IEnumerable<IEnumerable<T>> DifferentCombinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).DifferentCombinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
}
两个答案都很好,但可以通过消除内存分配来加快速度
对于答案1:现在从60计算5快2.5倍
编辑:EnumerableEx.Return
来自系统。交互式包装。
public static IEnumerable<IEnumerable<T>> DifferentCombinations2<T>
(this IEnumerable<T> elements, int k)
{
return k == 0
? EnumerableEx.Return(Enumerable.Empty<T>())
: elements.SelectMany((e, i) =>
elements.Skip(i + 1)
.DifferentCombinations(k - 1)
.Select(c => EnumerableEx.Return(e).Concat(c)));
}
答案2:从60计算5现在快3倍
static class Combinations
{
private static void SetIndexes(int[] indexes, int lastIndex, int count)
{
indexes[lastIndex]++;
if (lastIndex > 0 && indexes[lastIndex] == count)
{
SetIndexes(indexes, lastIndex - 1, count - 1);
indexes[lastIndex] = indexes[lastIndex - 1] + 1;
}
}
private static bool AllPlacesChecked(int[] indexes, int places)
{
for (int i = indexes.Length - 1; i >= 0; i--)
{
if (indexes[i] != places)
return false;
places--;
}
return true;
}
public static IEnumerable<IEnumerable<T>> GetDifferentCombinations<T>(this IEnumerable<T> c, int count)
{
var collection = c.ToList();
int listCount = collection.Count();
if (count > listCount)
throw new InvalidOperationException($"{nameof(count)} is greater than the collection elements.");
int[] indexes = Enumerable.Range(0, count).ToArray();
do
{
yield return indexes.Select(i => collection[i]).ToList();
SetIndexes(indexes, indexes.Length - 1, listCount);
}
while (!AllPlacesChecked(indexes, listCount));
}
}
这导致从60选5,答案2比答案1快5倍。
虽然上面的答案很简洁,但我想到了一个解决方案,根据集合大小可以更快。
static class Combinations
{
private static void InitIndexes(int[] indexes)
{
for (int i = 0; i < indexes.Length; i++)
{
indexes[i] = i;
}
}
private static void SetIndexes(int[] indexes, int lastIndex, int count)
{
indexes[lastIndex]++;
if (lastIndex > 0 && indexes[lastIndex] == count)
{
SetIndexes(indexes, lastIndex - 1, count - 1);
indexes[lastIndex] = indexes[lastIndex - 1] + 1;
}
}
private static List<T> TakeAt<T>(int[] indexes, IEnumerable<T> list)
{
List<T> selected = new List<T>();
for (int i = 0; i < indexes.Length; i++)
{
selected.Add(list.ElementAt(indexes[i]));
}
return selected;
}
private static bool AllPlacesChecked(int[] indexes, int places)
{
for (int i = indexes.Length - 1; i >= 0; i--)
{
if (indexes[i] != places)
return false;
places--;
}
return true;
}
public static IEnumerable<List<T>> GetDifferentCombinations<T>(this IEnumerable<T> collection, int count)
{
int[] indexes = new int[count];
int listCount = collection.Count();
if (count > listCount)
throw new InvalidOperationException($"{nameof(count)} is greater than the collection elements.");
InitIndexes(indexes);
do
{
var selected = TakeAt(indexes, collection);
yield return selected;
SetIndexes(indexes, indexes.Length - 1, listCount);
}
while (!AllPlacesChecked(indexes, listCount));
}
}