3

Note: This is a sequel to my previous question about powersets.

I have got a nice Ruby solution to my previous question about generating a powerset of a set without a need to keep a stack:

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

It does the job and works nice.

However, I would like to try to rewrite the same solution in Erlang, because for the {|item| p item} block I have a big portion of working code already written in Erlang (it does some stuff with each generated subset).

Although I have some experience with Erlang (I have read all 2 books :)), I am pretty confused with the example and the comments that sepp2k kindly gave me to my previous question about powersets. I do not understand the last line of the example - the only thing that I know is that is is a list comprehension. I do not understand how I can modify it to be able to do something with each generated subset (then throw it out and continue with the next subset).

How can I rewrite this Ruby iterative powerset generation in Erlang? Or maybe the provided Erlang example already almost suits the need?

Community
  • 1
  • 1
skanatek
  • 5,133
  • 3
  • 47
  • 75
  • Possibly insane question: Why do you want to generate the guy without a stack? The probably fastest version in Erlang keeps a stack proportional to the number of elements you are powersetting over. Note that in Erlang the stack is less limiting than in other languages. It will automatically grow and can't be exhausted easily. – I GIVE CRAP ANSWERS Dec 28 '11 at 17:25
  • I wanted to try to generate a powerset of a rather large set - more than 300 elements. But I don't need all of the subsets, so I tried to find a solution to generate a subset at a time and filter it out based on certain criteria. – skanatek Jan 03 '12 at 18:53

1 Answers1

1

All the given examples have O(2^N) memory complexity, because they return whole result (the first example). Two last examples use regular recursion so that stack raises. Below code which is modification and compilation of the examples will do what you want:

subsets(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2, N)),
    subsets(Lst, 0, N, Max).

subsets(Lst, I, N, Max) when I < Max ->
    _Subset = [lists:nth(Pos+1, Lst) || Pos <- lists:seq(0, N-1), I band (1 bsl Pos) =/= 0],
    % perform some actions on particular subset
    subsets(Lst, I+1, N, Max);
subsets(_, _, _, _) ->
    done.

In the above snippet tail recursion is used which is optimized by Erlang compiler and converted to simple iteration under the covers. Recursion may be optimized this way only if recursive call is the last one within function execution flow. Note also that each generated Subset may be used in place of the comment and it will be forgotten (garbage collected) just after that. Thanks to that neither stack nor heap won't grow, but you also have to perform operation on subsets one after another as there's no final result containing all of them.

My code uses same names for analogous variables like in the examples to make it easier to compare both of them. I'm sure it could be refined for performance, but I only want to show the idea.

Wacław Borowiec
  • 700
  • 1
  • 6
  • 12