情報共有と電話の回数 - 追記

NUM = ARGV.size==0 ? 4 : ARGV[0].to_i

def uniques( s )
  (0...s.size).map{ |i|
    if s[i] && (0...i).any?{ |j| s[i]==s[j] || ( s[i].size==1 && s[j] && s[j].size==1 ) }
      nil
    else
      i
    end
  }.select{ |x| x }
end

def each_pair(s0)
  vi = uniques( s0 )
  pairs={}
  vi.each{ |i|
    sj=s0.dup
    sj[i]=nil
    vj = uniques( sj )
    vj.each{ |j|
      key = [i+j, i*j]
      next if pairs[ key ]
      next if s0[i]==s0[j]
      pairs[key] = true
      yield( i, j )
    }
  }
end

def do_tel( s0, i, j )
  s=s0.dup
  s[i] = s[j] = (s[i]|s[j]).uniq.sort
  s
end

def share_done?( s )
  s.all?{ |x| x.size==NUM }
end

def count_tel( s0, pr, c )
  undone = s0.select{ |x| x.size<NUM }.size
  return if @best.size <= c+(undone+1)/2
  each_pair(s0){ |i,j|
    s = do_tel( s0, i, j )
    pr[c] = [i,j]
    if undone<=2 && share_done?( s ) then
      yield [pr,c]
      return
    else
      count_tel( s, pr, c+1 ){ |x| yield x }
    end
  }
end

def show( s )
  tel = s.map{ |x|
    "%c%c"%[x[0]+?a,x[1]+?a] 
  }.join( ' ' )
  puts "%2d:%s"%[ s.size, tel ]
  $stdout.flush 
end

require 'benchmark'
puts Benchmark.measure{
  @best = [0]*(NUM<5 ? NUM*2 : NUM*2-3)
  count_tel( (0...NUM).map{ |x| [x] }, [false]*@best.size, 0 ){ |pr,c|
    if c<@best.size then
      @best = pr[0,c+1]
      show @best
    end
  }
}

こんなので数えた。正しい？＞識者の方
手元で 8人 のときを数えたら 458秒かかった。たぶん、9人 の場合を数えると数時間かかる。
まだまだ枝を刈れるはずだが、いい方法が思いつかない。
ちなみに。変数 pr を使い回しているのは、高速化のため。
それと。

key = [i+j, i*j]

は、i, j のペアを、順序を無視して等しいかどうか調べるためのキー。
あ。

key = i+j + NUM*2*i*j

の方が速いか。とほほ。