How to efficently generate n different subsets of length k from List? I would like to generate n subsets from objects from a List. Each subset should have k elements. Each subset should be unique.

The output should be a List of Lists.

My (very very slow way) is to create ALL possible subsets:

public static IEnumerable&lt;IEnumerable&lt;T&gt;&gt; SubSetsOf&lt;T&gt;(IEnumerable&lt;T&gt; source)
{
    if (!source.Any())
        return Enumerable.Repeat(Enumerable.Empty&lt;T&gt;(), 1);

    var element = source.Take(1);

    var haveNots = SubSetsOf(source.Skip(1));
    var haves = haveNots.Select(set =&gt; element.Concat(set));

    return haves.Concat(haveNots);
}


Afterwards I select the subsets with length k with the help of linq .where(x =&gt; x.Count() == k) and randomly select n of them.

This is very slow, because if the input list has 50 elements, there are 1125899906842624 different possible subsets. This is a big overhead. 

How can I solve this problem more efficiently?
As noted in a comment, I did a series on my blog about interesting ways to solve this problem.  But let's think about simple ways we can modify your program to solve your problem.  We wish to produce all the subsets of source of size k, so let's add k to your method signature:

public static IEnumerable&lt;IEnumerable&lt;T&gt;&gt; SubSetsOf&lt;T&gt;(IEnumerable&lt;T&gt; source, int k)
{


All right, what is our base case?  Your original base case was "if the source is the empty set, then its only subset is the empty set".  We must modify that, because our new contract is that we only return subsets of size k.  

Let's be efficient. If k is zero then we can just take the early out; we know ahead of time that there is a subset of size zero regardless of the contents of source:

    if (k == 0)
        return Enumerable.Repeat(Enumerable.Empty&lt;T&gt;(), 1);


Now we know that k is not zero. If the source is empty, or k is negative, then there must be no solution:

    if (k &lt; 0 || !source.Any())
        return Enumerable.Empty&lt;IEnumerable&lt;T&gt;&gt;();


All right. That's our base case. 

Now we must modify your recursive case.  We now know that k is positive, and source is not empty.

There are two possibilities: either the first element is in the subset, or it is not. What are the subsets of size k that lack the first element?

    var haveNots = SubSetsOf(source.Skip(1), k);


Super. What are the subsets of size k that contain the first element? They are the subsets of size k-1 appended with that element.

    var element = source.Take(1);
    var smallerHaveNots = SubSetsOf(source.Skip(1), k-1);
    var haves = smallerHaveNots.Select(set =&gt; element.Concat(set));


And now we're done:

    return haves.Concat(haveNots);
}


A very small modification to your algorithm greatly speeds it up.  But we could make it more efficient still.  What if, instead of an IEnumerable&lt;T&gt; for source we had an ImmutableStack&lt;T&gt; for source?  The only operations that we ever perform on source are:


Is it empty?
Extract the head
Recurse on the tail


which is exactly the operations of an immutable stack. We could do this entire operation but allocation far fewer helper objects; each time you call Skip(1), that generates a new object, but there's no need to do that; you could just use the tail of the stack.

Similarly: the outputs are a sequence of possibly-empty tails that sometimes have a head pushed onto them; you can get efficiency wins by making the outputs also immutable stacks.

See if you can go from there and make a really efficient implementation of this algorithm.