原です。

「重複組合せ」でなく、「多重組合せ」のイテレータ化が気になったので書いて
みました。ここにメモします。

「多重組合せ」という用語は多分無くて、「n項係数」みたいなものです。2項係
数というは、nCmと書いて、(x+y)**n の展開に現れる x**m * y**(n-m)
の係数なわけですが、同様に3項係数は(x+y+z)**(p+q+r)に現れる x**p *
y**q * z**r の係数で、(p, q, r)と書いたりします。従って nCm は
(m, n-m)と書けます。

まず、2項係数は

|def comb(n, m = n)
|   if m == 0
|     yield([])
|   else
|     comb(n, m - 1) do |x|
|       ((x.empty? ? 0 : x.last + 1)...n).each do |i|
|	yield(x+[i])
|       end
|     end
|   end
|end

でイテレータ化できるわけですが、これは一般化しにくいので、さらに効率は悪
いのですが素朴な

def comb0(n, m = 0)
  if m == 0
    yield([])
  elsif n == m
    yield((0...n).to_a)
  else
    comb0(n - 1, m) do |x|
      yield(x.dup)
    end
    comb0(n - 1, m - 1) do |x|
      yield(x + [n-1])
    end
  end
end

を元にします。例えば

comb0(5, 3) do |x|
  p x
end

の結果は

[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]
[0, 1, 4]
[0, 2, 4]
[1, 2, 4]
[0, 3, 4]
[1, 3, 4]
[2, 3, 4]

です。これを多項化するために、出現したものに1、出現しなかったものに0を割り
振り、インデックスで次のように表現します。

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

そして、インデックスを 0, 1 だけでなく、一般に 0, 1,.. n にしたものが
最終的にほしいもので、次の様になりました。

def mcomb(a, s = (0...a.size).to_a)
  if a == []
    yield([])
  elsif i = a.index(0)
    (a = a.dup).slice!(i)
    (s = s.dup).slice!(i)
    mcomb(a, s) do |x|
      yield(x)
    end
  else
    a.each_index do |i|
      (b = a.dup)[i] -= 1
      mcomb(b, s) do |x|
	yield(x + [s[i]])
      end
    end
  end
end

mcomb([3, 2, 1]) do |x|
  p x #=>
end

[2, 1, 1, 0, 0, 0]
[1, 2, 1, 0, 0, 0]
[1, 1, 2, 0, 0, 0]
...
[0, 0, 1, 0, 1, 2]
[0, 0, 0, 1, 1, 2]
(計 (3+2+1)!/3!2!1! = 60個)

この mcomb を使って2項係数 comb 相当を書くと

def comb1(n, m)
  mcomb([n-m, m]) do |x|
    yield( (0...n).find_all{|i| x[i] == 1} )
  end
end

です。

順列組合せを総数だけでなく、各要素を列挙するアルゴリズムで示すには、イテ
レータは有効だ、というお話でした。