Generate a powerset with the help of a binary representation

Question

I know that "a powerset is simply any number between 0 and 2^N-1 where N is number of set members and one in binary presentation denotes presence of corresponding member".

(Hynek -Pichi- Vychodil)

I would like to generate a powerset using this mapping from the binary representation to the actual set elements.

How can I do this with Erlang?

I have tried to modify this, but with no success.

UPD: My goal is to write an iterative algorithm that generates a powerset of a set without keeping a stack. I tend to think that binary representation could help me with that.

Here is the successful solution in Ruby, but I need to write it in Erlang.

UPD2: Here is the solution in pseudocode, I would like to make something similar in Erlang.

Answer 1

First of all, I would note that with Erlang a recursive solution does not necessarily imply it will consume extra stack. When a method is tail-recursive (i.e., the last thing it does is the recursive call), the compiler will re-write it into modifying the parameters followed by a jump to the beginning of the method. This is fairly standard for functional languages.

To generate a list of all the numbers A to B, use the library method lists:seq(A, B).

To translate a list of values (such as the list from 0 to 2^N-1) into another list of values (such as the set generated from its binary representation), use lists:map or a list comprehension.

Instead of splitting a number into its binary representation, you might want to consider turning that around and checking whether the corresponding bit is set in each M value (in 0 to 2^N-1) by generating a list of power-of-2-bitmasks. Then, you can do a binary AND to see if the bit is set.

Putting all of that together, you get a solution such as:

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

However, you can also achieve the same thing using tail recursion without consuming stack space. It also doesn't need to generate or keep around the list from 0 to 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].

Note that when generating the list of subsets, you'll want to put new elements at the head of the list. Lists are singly-linked and immutable, so if you want to put an element anywhere but the beginning, it has to update the "next" pointers, which causes the list to be copied. That's why the helper function puts the Acc list at the tail instead of doing Acc ++ [generate_subset(...)]. In this case, since we're counting down instead of up, we're already going backwards, so it ends up coming out in the same order.

So, in conclusion,

1. Looping in Erlang is idiomatically done via a tail recursive function or using a variation of lists:map.
2. In many (most?) functional languages, including Erlang, tail recursion does not consume extra stack space since it is implemented using jumps.
3. List construction is typically done backwards (i.e., [NewElement | ExistingList]) for efficiency reasons.
4. You generally don't want to find the Nth item in a list (using lists:nth) since lists are singly-linked: it would have to iterate the list over and over again. Instead, find a way to iterate the list once, such as how I pre-processed the bit masks above.