Генерация powerset с помощью двоичного представления - PullRequest
Новая
       66

Генерация powerset с помощью двоичного представления

0 голосов
/ 26 декабря 2011

Я знаю, что «powerset - это просто любое число от 0 до 2 ^ N-1, где N - количество членов набора, а один в двоичном представлении означает наличие соответствующего члена».

( Гинек-Пичи- Виходил )

Я хотел бы сгенерировать powerset, используя это отображение из двоичного представления в фактические элементы набора.

Как я могу сделать это с Erlang?

Я пытался изменить это , но безуспешно.

UPD: Моя цель - написать итерационный алгоритм, который генерирует набор мощности набора без сохранения стека. Я склонен думать, что двоичное представление могло бы помочь мне в этом.

Здесь - успешное решение на Ruby, но мне нужно написать его на Erlang.

UPD2: Здесь - решение в псевдокоде, я хотел бы сделать что-то подобное в Erlang.

1 Ответ

3 голосов
/ 27 декабря 2011

Прежде всего, я хотел бы отметить, что в случае с Erlang рекурсивное решение не обязательно означает, что оно потребляет дополнительный стек.Когда метод является хвостово-рекурсивным (т. Е. Последнее, что он делает, это рекурсивный вызов), компилятор переписывает его для изменения параметров с последующим переходом к началу метода.Это довольно стандартно для функциональных языков.

Чтобы создать список всех чисел от A до B, используйте библиотечный метод lists:seq(A, B).

Для перевода списказначений (например, список от 0 до 2 ^ N-1) в другой список значений (например, набор, сгенерированный из его двоичного представления), используйте lists:map или понимание списка.

Вместо того, чтобы разбивать число на его двоичное представление, вы можете рассмотреть возможность его преобразования и проверки, установлен ли соответствующий бит в каждом значении M (от 0 до 2 ^ N-1)путем генерации списка степеней 2-битных масок.Затем вы можете выполнить двоичное И, чтобы увидеть, установлен ли бит.

Собрав все это вместе, вы получите решение, такое как: 

generate_powerset(List) ->
    % Do some pre-processing of the list to help with checks later.
    % This involves modifying the list to combine the element with
    % the bitmask it will need later on, such as:
    % [a, b, c, d, e] ==> [{1,a}, {2,b}, {4,c}, {8,d}, {16,e}]
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))],
    ListWithMasks = lists:zip(PowersOf2, List),

    % Generate the list from 0 to 1^N - 1
    AllMs = lists:seq(0, (1 bsl length(List)) - 1),

    % For each value, generate the corresponding subset
    lists:map(fun (M) -> generate_subset(M, ListWithMasks) end, AllMs).
    % or, using a list comprehension:
    % [generate_subset(M, ListWithMasks) || M <- AllMs].

generate_subset(M, ListWithMasks) ->
    % List comprehension: choose each element where the Mask value has
    % the corresponding bit set in M.
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0].

Однако вы также можете достичьто же самое, используя хвостовую рекурсию без использования стекового пространства.Также не нужно генерировать или хранить список от 0 до 2 ^ N-1. 

generate_powerset(List) ->
    % same preliminary steps as above...
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))],
    ListWithMasks = lists:zip(PowersOf2, List),
    % call tail-recursive helper method -- it can have the same name
    % as long as it has different arity.
    generate_powerset(ListWithMasks, (1 bsl length(List)) - 1, []).

generate_powerset(_ListWithMasks, -1, Acc) -> Acc;
generate_powerset(ListWithMasks, M, Acc) ->
    generate_powerset(ListWithMasks, M-1,
                      [generate_subset(M, ListWithMasks) | Acc]).

% same as above...
generate_subset(M, ListWithMasks) ->
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0].

Обратите внимание, что при создании списка подмножеств вы захотите поместить новые элементы вглава списка.Списки являются односвязными и неизменяемыми, поэтому, если вы хотите поместить элемент в любое место, кроме начала, он должен обновить указатели «next», что приведет к копированию списка.Вот почему вспомогательная функция помещает список Acc в хвост вместо выполнения Acc ++ [generate_subset(...)].В этом случае, так как мы ведем обратный отсчет, а не вверх, мы уже идем назад, и в итоге он выходит в том же порядке.

Итак, в заключение,

  1. Зацикливание в Erlang идиоматически выполняется через хвостовую рекурсивную функцию или с использованием вариации lists:map.
  2. Во многих (большинстве?) Функциональных языках, включая Erlang, хвостовая рекурсия не требует дополнительного места в стеке, посколькуреализован с использованием переходов.
  3. Построение списка обычно выполняется в обратном направлении (т. е. [NewElement | ExistingList]) из соображений эффективности.
  4. Обычно вы не хотите находить N-й элемент в списке (используяlists:nth), поскольку списки являются односвязными: придется повторять список снова и снова.Вместо этого найдите способ итерировать список один раз, например, как я предварительно обработал битовые маски выше.
...