如何生成给定大小的所有子集？
给定一些数字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> ）
这意味着我需要得到（subsetSize选择n）子集（牛顿符号）。
算法的任何想法可以找到我这样的整数列表列表？ 我正在用C＃实现它，如果这很重要的话。
internal class Program { private static IEnumerable> Subsets(int n, int subsetSize) { IEnumerable sequence = Enumerable.Range(1, n); // generate list of sequences containing only 1 element eg {1}, {2}, ... var oneElemSequences = sequence.Select(x => new[] { x }).ToList(); // generate List of int sequences var result = new List>(); // add initial empty set result.Add(new List ()); // 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> 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 ...
您可以使用位屏蔽alg。 该逻辑检查子集中元素的计数，每个唯一子集的总和并对结果进行排序。 这个是原始的，它可以优化为更好的exec。 可以消除速度和不需要的条件。
class Program { static void Main(string[] args) { int number, cntOfElements; int.TryParse(Console.ReadLine(), out number); int.TryParse(Console.ReadLine(), out cntOfElements); int[] intArray = Regex.Split(Console.ReadLine(), @"\s+").Select(int.Parse).Distinct().ToArray(); bool hasMatchingSubs = false; //The amount of possible combinations are 2 of power - the count of integers in the array //if they (the numbers) are 3 the combinations with the zero are 8 (in binary 0000 1000) //so we have 3 numbers and the bits before the setted bit of the 8 are the same count //this means that we can use them to get all the unique combinations for that amount of numbers //7 combinations without the zero (in binary 0000 0111). int combos = (int)Math.Pow(2, intArray.Length); List> result = new List>(); //we cicle around all the possible combinations for (int mask = 1; mask < combos; mask++) { int sum = 0; List list = new List (); //In the second for construction when the corresponding bit is set wi add this value //to the sum for this combination and when the bit is 0 we skip the adding for (int idx = 0; idx < intArray.Length; idx++) { if ((mask >> idx & 1) == 1) { sum += intArray[(intArray.Length - 1) - idx]; list.Add(intArray[(intArray.Length - 1) - idx]); } } //We are checking the sum for this combination before the next one if (sum == number && list.Count() == cntOfElements) { hasMatchingSubs = true; result.Add(list); } } if (!hasMatchingSubs) { Console.WriteLine("No matching subsets."); } else { result.ForEach(p => p.Sort()); //Sorting all elements in the inner lists result = result.OrderBy(a => a.Count).ThenBy(b => b.First()).ToList(); //ordering by the count of items in each list //and than by the value of the sirst integer result.ForEach(p => Console.WriteLine("{0} = {1}", string.Join(" + ", p), number)); } } }
您正在寻找的是没有重复的组合。 在链接下面应该是一个很好的起点：
http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-CG
您还需要一个递归实现。 否则，您将无法动态指定每组中的项目数。 在这里你可以找到一些进一步的解释：
我今天需要这个（我之前的解决方案效率太低）。 它比powerset方法更快。 它返回一个IEnumerable ，所以这应该是相对内存有效的，如果你不需要一次在内存中。
这就是我想出的：
public class Subsets { public static IEnumerable> Compute(int countOfSet, int countOfSubset) { if (countOfSet < 0) { throw new ArgumentException(@"countOfSet must be at least 0"); } if (countOfSubset < 0) { throw new ArgumentException(@"countOfSet must be at least 0"); } if (countOfSubset > countOfSet) { throw new ArgumentException(@"countOfSubset must less than or equal to countOfSet"); } //var allChoices = Enumerable.Range(0, countOfSet); //var result = GenerateOld(countOfSubset, allChoices, Enumerable.Empty()).ToArray(); var result = Generate(countOfSet, countOfSubset); return result; } public static IEnumerable> Generate(int countOfSet, int countOfSubset) { // If countOfSet is 5 and countofSubset is 3, maxCounterValue will be 234 var maxCounterValue = Enumerable.Range(0, countOfSet) .Reverse() .Take(countOfSubset) .Reverse() .ToArray(); var counters = new int[countOfSubset]; // Initialize counters to 0,1,2,3,... foreach (var i in Enumerable.Range(0, countOfSubset)) { counters[i] = i; } while (true) { yield return counters.ToArray(); if (counters.SequenceEqual(maxCounterValue)) { break; } var currentCounter = countOfSubset - 1; counters[currentCounter]++; // In case there was overflow, increment previous counters. while (counters[currentCounter] > maxCounterValue[currentCounter]) { currentCounter--; counters[currentCounter]++; } // "Reset" counters on the way back up. while (currentCounter < countOfSubset - 1) { counters[currentCounter + 1] = counters[currentCounter] + 1; currentCounter++; } } }
这是我的测试（NUnit 3）：
using NUnit.Framework; using System.Linq; //[Timeout(1000)] public class SubsetsTests { [Test] public void Compute0_1() { var act = new TestDelegate(() => Subsets.Compute(0, 1).ToArray()); Assert.That(act, Throws.Exception); } [Test] public void Compute_1_0() { var act = new TestDelegate(() => Subsets.Compute(-1, 0).ToArray()); Assert.That(act, Throws.Exception); } [Test] public void Compute1__1() { var act = new TestDelegate(() => Subsets.Compute(1, -1).ToArray()); Assert.That(act, Throws.Exception); } [Test] public void Compute0_0() { var result = Subsets.Compute(0, 0).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new int[0])); } [Test] public void Compute1_1() { var result = Subsets.Compute(1, 1).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new[] { 0 })); } [Test] public void Compute1_0() { var result = Subsets.Compute(1, 0).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new int[0])); } [Test] public void Compute2_2() { var result = Subsets.Compute(2, 2).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1 })); } [Test] public void Compute2_1() { var result = Subsets.Compute(2, 1).ToArray(); Assert.That(result.Length, Is.EqualTo(2)); Assert.That(result[0], Is.EquivalentTo(new[] { 0 })); Assert.That(result[1], Is.EquivalentTo(new[] { 1 })); } [Test] public void Compute2_0() { var result = Subsets.Compute(2, 0).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new int[0])); } [Test] public void Compute3_3() { var result = Subsets.Compute(3, 3).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1, 2 })); } [Test] public void Compute3_2() { var result = Subsets.Compute(3, 2).ToArray(); Assert.That(result.Length, Is.EqualTo(3)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1 })); Assert.That(result[1], Is.EquivalentTo(new[] { 0, 2 })); Assert.That(result[2], Is.EquivalentTo(new[] { 1, 2 })); } [Test] public void Compute3_1() { var result = Subsets.Compute(3, 1).ToArray(); Assert.That(result.Length, Is.EqualTo(3)); Assert.That(result[0], Is.EquivalentTo(new[] { 0 })); Assert.That(result[1], Is.EquivalentTo(new[] { 1 })); Assert.That(result[2], Is.EquivalentTo(new[] { 2 })); } [Test] public void Compute3_0() { var result = Subsets.Compute(2, 0).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new int[0])); } [Test] public void Compute4_4() { var result = Subsets.Compute(4, 4).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1, 2, 3 })); } [Test] public void Compute4_3() { var result = Subsets.Compute(4, 3).ToArray(); Assert.That(result.Length, Is.EqualTo(4)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1, 2 })); Assert.That(result[1], Is.EquivalentTo(new[] { 0, 1, 3 })); Assert.That(result[2], Is.EquivalentTo(new[] { 0, 2, 3 })); Assert.That(result[3], Is.EquivalentTo(new[] { 1, 2, 3 })); } [Test] public void Compute4_2() { var result = Subsets.Compute(4, 2).ToArray(); Assert.That(result.Length, Is.EqualTo(6)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1 })); Assert.That(result[1], Is.EquivalentTo(new[] { 0, 2 })); Assert.That(result[2], Is.EquivalentTo(new[] { 0, 3 })); Assert.That(result[3], Is.EquivalentTo(new[] { 1, 2 })); Assert.That(result[4], Is.EquivalentTo(new[] { 1, 3 })); Assert.That(result[5], Is.EquivalentTo(new[] { 2, 3 })); } [Test] public void Compute4_1() { var result = Subsets.Compute(4, 1).ToArray(); Assert.That(result.Length, Is.EqualTo(4)); Assert.That(result[0], Is.EquivalentTo(new[] { 0 })); Assert.That(result[1], Is.EquivalentTo(new[] { 1 })); Assert.That(result[2], Is.EquivalentTo(new[] { 2 })); Assert.That(result[3], Is.EquivalentTo(new[] { 3 })); } [Test] public void Compute5_5() { var result = Subsets.Compute(5, 5).ToArray(); Assert.That(result.Length, Is.EqualTo(1)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1, 2, 3, 4 })); } [Test] public void Compute5_4() { var result = Subsets.Compute(5, 4).ToArray(); Assert.That(result.Length, Is.EqualTo(5)); Assert.That(result[0], Is.EquivalentTo(new[] { 0, 1, 2, 3 })); Assert.That(result[1], Is.EquivalentTo(new[] { 0, 1, 2, 4 })); Assert.That(result[2], Is.EquivalentTo(new[] { 0, 1, 3, 4 })); Assert.That(result[3], Is.EquivalentTo(new[] { 0, 2, 3, 4 })); Assert.That(result[4], Is.EquivalentTo(new[] { 1, 2, 3, 4 })); } [Test] public void Compute5_3() { var result = Subsets.Compute(5, 3).ToArray(); Assert.That(result.Length, Is.EqualTo(10)); var i = 0; Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 1, 2 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 1, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 1, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 2, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 2, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 3, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 2, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 2, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 3, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 2, 3, 4 })); } [Test] public void Compute5_2() { var result = Subsets.Compute(5, 2).ToArray(); Assert.That(result.Length, Is.EqualTo(10)); var i = 0; Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 1 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 2 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 0, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 2 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 2, 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 2, 4 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 3, 4 })); } [Test] public void Compute5_1() { var result = Subsets.Compute(5, 1).ToArray(); Assert.That(result.Length, Is.EqualTo(5)); var i = 0; Assert.That(result[i++], Is.EquivalentTo(new[] { 0 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 1 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 2 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 3 })); Assert.That(result[i++], Is.EquivalentTo(new[] { 4 })); } }