あなたならどうお書きになります1.0 - 私の実装

実は。
娘の風邪でクリスマスパーティーは中止となり、今年はクリスマスパーティーのプレゼント交換はなくなった。とほほ。
それはともかく。あなたならどうお書きになります1.0( id:Nabetani:20061217 ) の締め切りなので書いておく。

実装の方針としては

全部数え上げて、そこから乱数で選ぶ。
適当に作ったパターンが条件に合致していたら終了。
ちゃんとやる。全部数え上げたりしない。

の三通りがあると思う。

(1)は、等確率であることが自明なのがいいところだが、人数が多くなると現実的な時間では終わらなくなる。
複数人数を含むグループがない場合は、n人で (n-1)! ぐらいになるので、14人ぐらいで 4G 通りを超えてしまう。jijixi さんが jijixi's diary - あなたならどうお書きになります1.0 (鍋あり谷あり) で

先に組み合わせを探索してそれからランダムに選ぶのが筋な気はするけど、なんとなくそれだと負けなような気がしたんだよぅ。

と指摘しているとおり、全部数えたら負けだと思う。

とはいえ、そういう実装も書いてみた:

class Array
  def each_perm
    if self.size<=1 then
      yield self
    else
      size.times{ |i|
        ( self[ 0...i ]+self[(i+1)..-1] ).each_perm{ |x|
          yield [self[i]]+x
        }
      }
    end
  end
end

def each_exchange( a )
  ix=0
  a.each_perm{ |to|
    if ( (0...a.size).all?{ |i| a[i][0]!=to[i][0] } )
      ix+=1
      yield ix, to
    end
  }
end


a=ARGV
ok=0
each_exchange( a ){ ok+=1 }

puts "candidates:#{ok}"
t = rand(ok)
each_exchange( a ){ | ix, to |
  if t==ix
    puts a.zip(to).map{ |x| "#{x[0]}->#{x[1]}" }.join( ', ' )
    break
  end
}

実際のところこれはちょっと数えすぎで、もっと効率よく動かすことが出来るが、それにしても現実的な時間に計算が終わらないことにはかわりがない。

(2)は、

解がない場合に一生終わらない
解があっても運が悪いと百万年かかる

などの致命的っぽい欠陥があるものの、現実のクリスマスパーティーを考えるとこの実装が必要にして十分だと思えた。
この実装を採用しているのは http://d.hatena.ne.jp/shinichiro_h/20061221/1166649644 だが、計算内容が題意とは若干異なる。題意に合わせて書き直すと

a=ARGV
loop{
  r=a.zip( a.sort_by{ rand } )
  if r.all?{ |x| x[0][0]!=x[1][0] }
    puts r.map{ |x| x.join( '→' ) }.join( ', ' )
    exit
  end
}

こんな感じ。10人のグループが2つだったりすると現実的な時間では終わらなくなってしまうが、そんなクリスマスパーティーはあまりない。
ちょっとゴルフ気味なので、名前の1文字目をグループ名にするというやや野蛮な実装になっている。
私はこれが一番好き。

(3)がもともと私が考えていた実装で、自分で書いてみて面白かったのでこうして出題してみた。
最初 ActionScript で書こうとしたんだが、頭が整理できなくなったので、 ruby で書いた。そしたらまあまあすぐに書けた。言語の力の違いだなと思うが、慣れの問題かもしれない。

で。私が書いたのは

ExchInfo = Struct.new( :gr, :name, :to )
class ExchInfo
  def dispname; gr!=name ? gr+':'+name : name; end
end

def find_exchange( exchinfo, ix, not_given )
  if not_given.empty?
    throw :found, exchinfo.sort_by{ |i| i.dispname }.map{ |i|
      "#{i.dispname} -> #{exchinfo[ i.to ].dispname}"
    }.join( ', ' )
  end
  not_given.sort_by{ rand(0) }.each{ |to|
    next if exchinfo[to].gr == exchinfo[ix].gr
    exchinfo[ix] = exchinfo[ix].dup
    exchinfo[ix].to = to
    find_exchange( exchinfo, ix+1, not_given-[to] )
  }
end

members = ARGV
#members = (1..50).map{ |i| %w(a b).map{ |g| "#{g}:#{g}#{i}" } }.flatten

exchinfo = members.map{ |m|
  s=m.split(':')
  ExchInfo.new( s[0], s.size==1?s[0]:s[1], nil )
}.sort_by{ rand(0) }

result = catch( :found ){
  find_exchange( exchinfo.dup, 0, (0...members.size).to_a )
  "no solution found."
}
puts result

こんな感じ。初めて Struct を使ったような気がする。
入力は

ruby 鍋谷:武典鍋谷:杏子出部穴田野庭

という感じ。
これなら 50人のグループが2つでも一瞬で計算が終わる。
入力はコマンドライン引数で、空白区切り。コロンの前がグループ名。コロンがなければ自分自身のみのグループ。

この実装の欠点は

ソースが長い
等確率であるかどうかがよくわからない

の2点。たぶん、仕事で書くならこれを書くしかないと思う。

で。
実装してくださった方のソースを見たんだが、私の知らない処理系で書かれたものが多く、読めなかった。すいません。
ruby のは読んだけど。

あと。
最初に書いた三通り以外の実装を目指していると思われる id:another:20061224:1166957804 に関連して。
[ [a1, a2, a3], [b1, b2, b3], c1, d1] の時、2196=2*2*3*3*61 通りなので、きれいにループを書くのは無理だと思う。