首页 / C# / c# – 如何生成给定大小的所有子集?
c# – 如何生成给定大小的所有子集?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c# – 如何生成给定大小的所有子集?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1644字,纯文字阅读大概需要3分钟。
内容图文
![c# – 如何生成给定大小的所有子集?](/upload/InfoBanner/zyjiaocheng/779/ee99ae22dd78496c953242e1a99e9cfe.jpg)
给定一些数字n和一个子集大小,我想获得集合{1,…,n}的指定大小的所有可能子集.
对于n = 5和subsetSize = 4的预期结果:
{{1,2,3,4}, {1,2,3,5}, {1,3,4,5}, {1,2,4,5}, {2,3,4,5}}
(这将是一个List< List< int>>)
这意味着我需要得到(subsetSize选择n)子集(牛顿符号).
算法的任何想法可以找到我这样的整数列表列表?我正在用C#实现它,如果这很重要的话.
解决方法:
internal class Program
{
private static IEnumerable<IEnumerable<int>> Subsets(int n, int subsetSize)
{
IEnumerable<int> sequence = Enumerable.Range(1, n);
// generate list of sequences containing only 1 element e.g. {1}, {2}, ...
var oneElemSequences = sequence.Select(x => new[] { x }).ToList();
// generate List of int sequences
var result = new List<List<int>>();
// add initial empty set
result.Add(new List<int>());
// generate powerset, but skip sequences that are too long
foreach (var oneElemSequence in oneElemSequences)
{
int length = result.Count;
for (int i = 0; i < length; i++)
{
if (result[i].Count >= subsetSize)
continue;
result.Add(result[i].Concat(oneElemSequence).ToList());
}
}
return result.Where(x => x.Count == subsetSize);
}
private static void OutputSubset(int n, IEnumerable<IEnumerable<int>> subsets)
{
Console.WriteLine("n: {0}", n);
foreach (var subset in subsets)
{
Console.WriteLine("\t{0}", string.Join(" ", subset.Select(x => x.ToString())));
}
}
private static void Main()
{
for (int n = 1; n < 500; n++)
{
var subsets = Subsets(n, subsetSize: 4);
OutputSubset(n, subsets);
}
}
}
输出:
n: 1
n: 2
n: 3
n: 4
1 2 3 4
n: 5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
n: 6
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
1 2 3 6
1 2 4 6
1 3 4 6
2 3 4 6
1 2 5 6
1 3 5 6
2 3 5 6
1 4 5 6
2 4 5 6
3 4 5 6
n: 7
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
1 2 3 6
...
内容总结
以上是互联网集市为您收集整理的c# – 如何生成给定大小的所有子集?全部内容,希望文章能够帮你解决c# – 如何生成给定大小的所有子集?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源:【匿名】