如何生成给定大小的所有子集？ [英] How to generate all subsets of a given size?

问题描述

给出一些数字n和一个子集大小，我想获取集合{1，...，n}中指定大小的所有可能子集。

Given some number n, and a subset size, I want to get all possible subsets of the specified size of the set {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）个子集（牛顿符号）。

That means I need to get (subsetSize choose n) subsets (Newton's symbol).

对算法有任何想法，可以找到这样的整数列表吗？

Any idea for an algorithm that could find me such a list of lists of integers? I'm implementing it in C#, if that matters.

推荐答案

您可以使用位屏蔽算法。该逻辑检查子集中元素的数量，每个唯一子集的总和，并对结果进行排序。这是原始的，可以对其进行优化以获得更好的执行力。

You can use the bit masking alg. This logic checks for the count of the elements in the subset, the sum of each unique subset and sorts the result. This one is raw and it can be optimised for better exec. speed and the unneeded conditions can be removed.

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));
        }
    }
}

这篇关于如何生成给定大小的所有子集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！