「プログラマ脳を鍛える数学パズル」の Q30 がわかりません

Question

「プログラマ脳を鍛える数学パズル」という本に載っている
「Q30 テーブルタップで作るタコ足配線」の解答コードが理解できません。
どなたかコードのアルゴリズムを解説していただけないでしょうか？

問題は以下です。

口数が2つと3つのテーブルタップを組み合わせてぴったりN個の空いている口を作る。
N＝20の時、作れるパターン数を求めよ。
(ただし、同じテーブルタップに挿す場合、挿す場所によっての場合分けは考えない)

例としN=4の場合、下図のように4パターン作ることが出来る。

解答のコードは以下です

N = 20

@memo = {1 => 1}
def set_tap(remain)
  return @memo[remain] if @memo.has_key?(remain)
  cnt = 0
  # 2口
  (1..(remain / 2)).each{|i|
    if remain - i == i then
      cnt += set_tap(i) * (set_tap(i) + 1) / 2
    else
      cnt += set_tap(remain - i) * set_tap(i)
    end
  }
  # 3口
  (1..(remain / 3)).each{|i|
    (i..((remain - i) / 2)).each{|j|
      if (remain - (i + j) == i) && (i == j) then
        cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6
      elsif remain - (i + j) == i then
        cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2
      elsif i == j  then
        cnt += set_tap(remain - (i+j)) * set_tap(i) * (set_tap(i)+1) / 2
      elsif remain - (i + j) == j then
        cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2
      else
        cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
      end
    }
  }
  @memo[remain] = cnt
end

puts set_tap(N)

2口や3口の場合の初めに書いてある

(1..(remain / 2)) や (1..(remain / 3)) が

タップの必要となる最大の個数？かとも思ったのですが、その後の場合分けも含め、全く理解できません。

どなたか解説宜しくお願いします。

Answer 1

コードを読む限り、最初に差し込み口が一つだけある場合にremain個の差し込み口をつくる場合の数を求めてるんだと思います。
'#2口とコメントが書かれてるブロックは、その最初の差し込み口に2つ差し込み口のあるタップをつけるときの場合の数で
'#3口とコメントが書かれているブロックは、その最初の差し込み口に3つ差し込み口のあるタップをつけるときの場合の数です。

新たに差し込み口が増えたので、それらの差し込み口をそれぞれを最初の一つとして再帰的に問題を解いていくことで全体の場合の数が計算できます。

試しにN==4について解くと、最初に2口のタップを挿した場合それぞれの差し込み口を使って(1, 3), (2, 2)個の差し込み口を作ると合計で4個の差し込み口が作れます(どの差し込み口に差すかで区別しないので、(3, 1)などは考えない)
図でいうところの上二つが(1, 3)のパターンで、左下が(2, 2)のパターンです。
最初に3口のタップを挿した場合は(1, 1, 2)のパターンしかありません。図でいうところの右下のパターン。

それを踏まえてコードにコメントをつけるとこんな感じです。

N = 20

@memo = {1 => 1}
def set_tap(remain)
  return @memo[remain] if @memo.has_key?(remain)
  cnt = 0
  # 2口
  (1..(remain / 2)).each{|i| #2口の差し込み口のうち少ない数を割り当てる方の割り当て数。remain - i はもう一つの差し込み口に割り当てる数。
    if remain - i == i then #両方の差し込み口に同じ数が割り当てられる場合、差し込み口を入れ替えただけのものを重複してカウントしないようにする。
      cnt += set_tap(i) * (set_tap(i) + 1) / 2
    else #そうでない場合、そのまま両方の組み合わせの積をカウント。
      cnt += set_tap(remain - i) * set_tap(i)
    end
  }
  # 3口
  (1..(remain / 3)).each{|i| #3口の差込口のうち、一番小さい数を割り当てる物の割り当て数。残りはremain - i。
    (i..((remain - i) / 2)).each{|j| #残り2口の差し込み口のうち、小さい数を割り当てるの割り当て数。残りはremain - (i + j)。
      #2口の場合と同じく、差し込み口を入れ替えたものを重複してカウントしないようにする場合分け。
      if (remain - (i + j) == i) && (i == j) then #全部の差し込み口に同じ数を割り当てる場合。
        cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6
      elsif remain - (i + j) == i then # i <= j <= remain (i + j) なので本当はいらない。
        cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2
      elsif i == j  then #小さいほう二つに同じ数を割り当てる場合。
        cnt += set_tap(remain - (i+j)) * set_tap(i) * (set_tap(i)+1) / 2
      elsif remain - (i + j) == j then #大きいほう二つに同じ数を割り当てる場合。
        cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2
      else #3つとも違う数を割り当てる場合。
        cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
      end
    }
  }
  @memo[remain] = cnt
end

puts set_tap(N)

Comments

[pyxis]

丁寧な解答ありがとうございました。
理解できました。

それぞれの挿し口の空きの合計が同じ場合は重複組み合わせになっているので、
set_tap(i)種のものから2個選ぶと考えれば重複組み合わせの公式より
(set_tap(i)+2-1)C2となり、それをコードにすると
set_tap(i) * (set_tap(i) + 1) / 2

同様に3口でそれぞれの口で空き数が同じ場合は
(set_tap(i)+3-1)C3なので、それをコードにすると
set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6 となっているのですね。