Translating function for finding all partitions of a set from Python to Ruby

python, ruby

Solution

#!/usr/bin/ruby1.8

def partitions(set)
  yield [] if set.empty?
  (0 ... 2 ** set.size / 2).each do |i|
    parts = [[], []]
    set.each do |item|
      parts[i & 1] << item
      i >>= 1
    end
    partitions(parts[1]) do |b|
      result = [parts[0]] + b
      result = result.reject do |e|
        e.empty?
      end
      yield result
    end
  end
end

partitions([1, 2, 3, 4]) do |e|
  p e
end

# => [[1, 2, 3, 4]]
# => [[2, 3, 4], [1]]
# => [[1, 3, 4], [2]]
# => [[3, 4], [1, 2]]
# => [[3, 4], [2], [1]]
# => [[1, 2, 4], [3]]
# => [[2, 4], [1, 3]]
# => [[2, 4], [3], [1]]
# => [[1, 4], [2, 3]]
# => [[1, 4], [3], [2]]
# => [[4], [1, 2, 3]]
# => [[4], [2, 3], [1]]
# => [[4], [1, 3], [2]]
# => [[4], [3], [1, 2]]
# => [[4], [3], [2], [1]]

What's different:

- The guard calls set.empty? instead of (implicitly) testing for set.nil?

- Leave out the .each when calling partitions

- Use Array instead of Set

- Filter empty sets out of the yielded result

Problem

I have the following python function to recursively find all partitions of a set: ``` def partitions(set_): if not set_: yield [] return for i in xrange(2**len(set_)/2): parts = [set(), set()] for item in set_: parts[i&1].add(item) i >>= 1 for b in partitions(parts[1]): yield [parts[0]]+b for p in partitions(["a", "b", "c", "d"]): print(p) ``` Can someone help me to translate this into ruby? This is what I have so far: ``` def partitions(set) if not set yield [] return end (0...2**set.size/2).each { |i| parts = [Set.new, Set.new] set.each { |item| parts[i&1] << item i >>= 1 } partitions(parts[1]).each { |b| yield [parts[0]] << b } } end p partitions([1, 2, 3, 4].to_set) ``` I get the error "LocalJumpError: no block given". I guess this is because the yield functions work differently in Python and Ruby.

Original source