From: Shin-ichro Hara <sinara@...>
Date: 1998-10-31T16:15:17+09:00
Subject: [ruby-list:10532] Re: SuperEnumerable

原です。

In message "[ruby-list:10459] SuperEnumerable"
    on 98/10/29, Shin-ichro Hara <sinara@blade.nagaokaut.ac.jp> writes:

|悪ノリして「超 Enumerable」というのを考えて見ました。

悪ノリついでに、ひわださんの、

In message "[ruby-list:10481] Enumerable#collect bug?"
    on 98/10/30, Kazuhiro HIWADA <hiwada@kuee.kyoto-u.ac.jp> writes:

|class CombinationIterator

という combinatorial な iterator を考えてみました。

まず部分集合全体は次の power_set で表現できます。

module Enumerable
  def power_set
    collect{ |x| [nil, x] }.s_collect{ |*y| y.compact }
  end
end

dat = ["a","b","c","d"].power_set
([0..1] * 4).s_each { |*x| p dat.at(*x) }

つまり (1+a)(1+b)(1+c)(1+d) の展開をしているわけです。
後はこれを要素の個数毎に分類すれば、求めるものです。

module Enumerable
  def sub_sets
    ary = (0..size).collect{ [] }
    collect{ |x| [nil, x] }.s_each{ |*y|
      z = y.compact
      ary[z.size].push z
    }
    ary
  end
end

sset = ["a","b","c","d"].sub_sets
(0..4).each { |i| p sset[i] }

最終的に、要素数 n の部分集合に対する each は

module Enumerable
  def comb_each(n)
    sub_sets[n].each{ |x| yield(x) }
  end
end

[1,2,3].comb_each(2) { |x| p x }

となるわけですが、sub_sets の値を使い回さないこの場面では効率
は悪いです。