如何生成给定大小的所有子集
本文关键字：子集 何生成 | 更新日期: 2023-09-27 18:06:00
给定某数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 choose 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
...
您可以使用位屏蔽算法。该逻辑检查子集中元素的计数、每个唯一子集的和并对结果进行排序。这是一个原始的，它可以优化更好的执行。速度和不需要的条件可以去除。
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<List<int>> result = new List<List<int>>();
//we cicle around all the possible combinations
for (int mask = 1; mask < combos; mask++)
{
int sum = 0;
List<int> list = new List<int>();
//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-C-G还需要递归实现。否则，您将无法动态指定每个集合中的项数。你可以在这里找到一些进一步的解释:
http://erwinmayer.com/2010/12/14/recursive-algorithm-to-generate-all-combinations-of-elements-in-arrays/我今天需要这个(我以前的解决方案效率太低)。它比powerset方法快。它返回一个IEnumerable，所以如果您不需要它们一次都在内存中，这也应该是相对有效的。
这是我想到的:
public class Subsets
{
public static IEnumerable<IList<int>> 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<int>()).ToArray();
var result = Generate(countOfSet, countOfSubset);
return result;
}
public static IEnumerable<IList<int>> 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 }));
}
}
我创建了以下IEnumerable扩展方法来获取数组中大小为n的所有子集，并可选择一个谓词。
public static class ExtensionMethods
{
public static IEnumerable<IEnumerable<T>> GetSubSets<T>(this IEnumerable<T> list, int size, Predicate<T> filter)
{
return GetSubSetsInternal(list.ToList().FindAll(filter), size);
}
public static IEnumerable<IEnumerable<T>> GetSubSets<T>(this IEnumerable<T> list, int size)
{
return GetSubSetsInternal(list, size);
}
private static IEnumerable<IEnumerable<T>> GetSubSetsInternal<T>(this IEnumerable<T> list, int size)
{
var vFinalList = new List<IList<T>>();
var c = size;
var vList = list.ToList();
var vListSize = list.Count();
if (c <= 0 || size > vListSize) return vFinalList;
c -= 1;
var indexs = new int[size];
var vFirstSubList = new List<T>();
for (var j = 0; j <= (size - 1); j++)
{
indexs[j] = j;
vFirstSubList.Add(vList[j]);
}
vFinalList.Add(vFirstSubList);
while (indexs[0] !=(vListSize - size) && vFinalList.Count < 2147483647)
{
if (indexs[c] < c + (vListSize - size))
{
indexs[c]++;
var vSubList = new List<T>();
foreach (var j in indexs) vSubList.Add(vList[j]);
vFinalList.Add(vSubList);
}
else
{
do
{
c -= 1;
} while (indexs[c] == c + (vListSize - size));
indexs[c] += 1;
for (var j = c + 1; j <= (size - 1); j++) indexs[j] = indexs[j - 1] + 1;
var vSubList = new List<T>();
foreach (var j in indexs) vSubList.Add(vList[j]);
vFinalList.Add(vSubList);
c = size - 1;
}
}
return vFinalList;
}
}
用法:例如确定数独游戏中的裸集。
internal class SolverStepNakedSet : SolverStepSetBase
{
protected override bool SolveIt(SolutionManager solutionManager, int size)
{
foreach (var vSol in (from vec in solutionManager.Sudoku.Vectors
from vSet in vec.GetSubSets(size, c => Enumerable.Range(2, size - 1).Contains(c.MyValue.OpenCandidates.Count()))
let vValues = vSet.SelectMany(c => c.MyValue.OpenCandidates).Select(cc=> cc.Value).Distinct().ToList()
where vValues.Count() == size
let vLstCellsValues = (from vValue in vValues
let vLstCells = vec.FindAll(c => !vSet.Contains(c) && c.MyValue.OpenCandidates.Any(cc=>cc.Value==vValue))
where vLstCells.Count() > 0
select new SolutionValueElement(vValue, vLstCells))
where vLstCellsValues.Count() > 0
select new SolutionSet( Step, new SolutionValue(ValueState.Removal, vLstCellsValues), new Set(vSet.ToList(),vValues))))
{
if (solutionManager.Execute(vSol)) return true;
}
return false;
}
}