Сгенерируйте силовую схему с помощью двоичного представления

Question

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

(Hynek -Pichi- Vychodil)

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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