Generate a Powerset of a Set Without Keeping a Stack in Erlang or Ruby

Generate a powerset of a set without keeping a stack in Erlang or Ruby

Edit: Added the enumerator (as @Jörg W Mittag) if no block is given.

class Array
  def powerset
    return to_enum(:powerset) unless block_given?
    1.upto(self.size) do |n|
      self.combination(n).each{|i| yield i}
    end
  end
end
# demo
['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time
ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 
10.times.map{ ps.next } # 10.times without a block is also an enumerator

Output

["a"]
["b"]
["c"]
["a", "b"]
["a", "c"]
["b", "c"]
["a", "b", "c"]
[[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Generate permutations iteratively without recursion or stack with Ruby/Erlang

Ruby's Array.permutation.to_a does indeed produce an array. Don't use to_a then! It means 'to array'. Array.permutation gives you an 'enumerator', a generator. Since you want to throw out most permutations, use reject on it.

res = [1,2,3,4].permutation(3).reject do |perm|
  perm.first.even? #if this line is true, the perm will be rejected
end

will generate all permutations of three elements and reject those with an even number on the first position. But ehm... have you seen how much 300! is?

Generate all unique subsets of a set (not a powerset)

It sounds like what you are looking for are the partitions of a set/array.

One way of doing this is recursively:

• a 1 element array [x] has exactly one partition
• if x is an array of the form x = [head] + tail, then the partitions of x are generated by taking each partition of tail and adding head to each possible. For example if we were generating the partitions of [3,2,1] then from the partition [[2,1]] of [2,1] we can either add 3 to to [2,1] or as a separate element, which gives us 2 partitions [[3,2,1] or [[2,1], [3]] of the 5 that [1,2,3] has

A ruby implementation looks a little like

def partitions(x)
  if x.length == 1
   [[x]]
  else
    head, tail = x[0], x[1, x.length-1]
    partitions(tail).inject([]) do |result, tail_partition|
      result + partitions_by_adding_element(tail_partition, head)
    end
  end
end

def partitions_by_adding_element(partition, element)
  (0..partition.length).collect do |index_to_add_at|
    new_partition = partition.dup
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element]
    new_partition
  end
end

Generate a powerset with the help of a binary representation

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.

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

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.

Distributed Powerset

If you use n bits of an integer to represent the items in a subset of n items, you can start the variable at 0, and increment it to get to the next subset. So to evenly distribute the work between k processors, you can simply have processor #i start its integer variable at i and add k to it on each step. Every subset will be processed by exactly one processor.

Bear in mind that this won't do very much to help you solve large problems. If you can solve a problem of size x on a single computer (and I'd estimate 20 <= x <= 30 on today's computers, roughly), then even by buying 1024 computers you would only be able to solve a problem of size x+10.

Ruby Combinations with array elements

There is a trivial correspondence (bijection) between such combinations and the numbers in [1..(2^m - 1)] (m being the array length).

Consider such a number n. It's binary representation has m digits (including leading zeros). The positions of the digits that are 1 are the indices of the elements in the corresponding combination.

The code would be:

def combinations(array)
  m = array.length
  (1...2**m).map do | n |
    (0...m).select { | i | n[i] == 1 }.map { | i | array[i] }
  end
end

---

Related Topics