Generate a powerset of a set containing only subsets of a certain size

Question

I would like to generate a powerset P(S) of a set S. I would like P(S) to have only subsets equal to a certain size.

For example, if we have S = [1,2,3,4], then limited_powerset(S,3) will be [[1,2,3],[2,3,4],[1,3,4],[1,2,4]].

Hynek Pichi Vychodil has provided a nice example of general powerset generation in Erlang (thanks!):

generate([]) -> [[]];
generate([H|T]) -> PT = generate(T),
  generate(H, PT, PT).

generate(_, [], Acc) -> Acc;
generate(X, [H|T], Acc) -> generate(X, T, [[X|H]|Acc]).

How can I modify it to have only subsets of a certain size? Introducing a Limit variable and changing the last line to

case length([X|H]) < Limit of
        true -> 
            ps(X, T, Acc, Limit);
        false -> 
            ps(X, T, [[X|H]|Acc],Limit)
    end.

doesn't help.

P.S. I guess that the number of subsets will be less than N!, but how can I calculate it exactly?

Answer 1

This will do what you want:

limited_powerset(L, N) ->
  {_, Acc} = generate(L, N),
  Acc.

generate([], _) ->
  {[[]], []};
generate([H|T], N) ->        
  {PT, Acc} = generate(T, N),
generate(H, PT, PT, Acc, N).

generate(_, [], PT, Acc, _) -> 
  {PT, Acc};
generate(X, [H|T], PT, Acc, N) when length(H)=/=N-1 ->
  generate(X, T, [[X|H]|PT], Acc, N);
generate(X, [H|T], PT, Acc, N) ->    
  generate(X, T, [[X|H]|PT], [[X|H]|Acc], N).

It's not trivial. It had me stumped for a while. The trick is that you need to maintain the full powerset accumulator throughout the algorithm and create a second accumulator for the limited set.