How to generate all subsets of a given size?

Question

Given some number n, and a subset size, I want to get all possible subsets of the specified size of the set {1, ..., n}.

Expected result for for n = 5 and subsetSize = 4:

{{1,2,3,4}, {1,2,3,5}, {1,3,4,5}, {1,2,4,5}, {2,3,4,5}}

(that would be a List<List<int>>)

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.

Answer 1

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

Output:

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
        ...