与特定数字不重复的组合
与特定数字不重复的组合
提问于 2017-06-30 19:23:41
我想要找到所有10个没有重复的元素组合，例如，如果我们有一个数组[0,1,2,3,4]，我想要找到所有没有重复的包含数字0的三元素组合，我会得到以下结果：0,1,2; 0,1,3; 0,1,4; 0,2,3; 0,2,4; 0,4,3;
搜索方法应该是快速找到所有组合，然后过滤太长，例如，搜索k= 10 n= 64的组合会给出151473214816组合，并生成内存不足异常(16 i7内存，i7 7600U)
此方法花费的时间太长。
要搜索所有组合，例如当使用k = 2或k = 3时，我使用以下方法：
public static IEnumerable<IEnumerable<T>> GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
{
if (length == 1)
{
return list.Select(t => new T[] { t });
}
else
{
return GetKCombs(list, length - 1).SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), (t1, t2) => t1.Concat(new T[] { t2 }));
}
}我应该如何修改这个方法，以只选择包含特定数字的组合，或者它应该如何看起来是新的？
也许该方法不应该搜索所有可能的组合，然后只对它们进行过滤以重新创建它们自己(递归？)只有那些有特定编号的，但我不知道如何编写这样的方法或修改现有的方法。
有人能帮我解决这个问题吗？
回答 1
Stack Overflow用户
发布于 2017-06-30 19:32:53
我使用这个方法：
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
}这将仅返回具有特定实例的组合：
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k, T instance)
{
if( k == 0 || !elements.Contains(instance)) return new[] { new T[0] };
return elements.Where(x => !Equals(x, instance)).Combinations(k - 1).Select(c => (new[] {instance}).Concat(c));
}想法很简单:从list中获取所有组合(k-1个元素)，不包括实例，并将实例添加到结果中。
我从来没有检查过它的性能。如果你愿意，你可以试一试，并分享你的结果。虽然组合的数量应该是相同的，但我不希望这些方法有什么大的不同。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44845322
复制相关文章
相似问题
腾讯云开发者
