Генерация powerset набора, содержащего только подмножества определенного размера - PullRequest
Новая
       39

Генерация powerset набора, содержащего только подмножества определенного размера

1 голос
/ 14 ноября 2011

Я хотел бы сгенерировать powerset P(S) из набора S.Я бы хотел, чтобы P(S) имел только подмножества, равные определенному размеру.

Например, если у нас есть S = [1,2,3,4], то limited_powerset(S,3) будет [[1,2,3],[2,3,4],[1,3,4],[1,2,4]].

Hynek Pichi Vychodil предоставил хороший пример генерации общего набора мощности в Erlang (спасибо!): 

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

Как я могу изменить его, чтобы иметь только подмножества определенного размера? Введение переменной Limit и изменение последней строки на 

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

не помогает.

PS Я предполагаю, что количество подмножеств будет меньше, чем N !, но как я могуточно рассчитать?

1 Ответ

3 голосов
/ 15 ноября 2011

Это будет делать то, что вы хотите: 

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

Это не тривиально.Это поставило меня в тупик на некоторое время.Хитрость заключается в том, что вам нужно поддерживать полный аккумулятор powerset на протяжении всего алгоритма и создавать второй аккумулятор для ограниченного набора.

...