#!/usr/bin/ruby1.8def 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 endendpartitions([1, 2, 3, 4]) do |e| p eend# => [[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]]
有什么不同：
- 守卫打电话给set.empty？而不是（隐式）测试set.nil？
- 调用分区时忽略.each
- 使用数组而不是Set
- 从产生的结果中过滤出空集
