Hatena::ブログ(Diary)

脱エンタープライズ志向 このページをアンテナに追加 RSSフィード

2009-06-12

第4回プログラマの数学読書会を主宰してきたー

| 00:02 | 第4回プログラマの数学読書会を主宰してきたーを含むブックマーク

6月6日(土)自らが主宰する第4回プログラマ数学読書会を開催してきた。

今回はなんと3人もの新しいメンバーが参加してくれた。ありがとうございます。

まだ第4回だが、内容は既に終盤で次回で読了する予定。ということで今回は5、6章を勉強した。

id:Nabetaniさんの提供問題

MLから抜粋。以下のすべてid:Nabetaniさん提供の問題です、ありがとうございます!

問題

正の整数aとbを受け取り、1からaまでの整数から重複なくb個を選ぶ選び方をすべて出力するプログラムを書け。

出力順は問わない。また、不正な入力(範囲外、非整数、負の数など)に対する対応はしなくて良い。

実行例:

>combi 6 3

1 2 3

1 2 4

1 2 5

1 2 6

1 3 4

1 3 5

1 3 6

1 4 5

1 4 6

1 5 6

2 3 4

2 3 5

2 3 6

2 4 5

2 4 6

2 5 6

3 4 5

3 4 6

3 5 6

4 5 6

>combi 8 6

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 5 8

1 2 3 4 6 7

1 2 3 4 6 8

1 2 3 4 7 8

1 2 3 5 6 7

1 2 3 5 6 8

1 2 3 5 7 8

1 2 3 6 7 8

1 2 4 5 6 7

1 2 4 5 6 8

1 2 4 5 7 8

1 2 4 6 7 8

1 2 5 6 7 8

1 3 4 5 6 7

1 3 4 5 6 8

1 3 4 5 7 8

1 3 4 6 7 8

1 3 5 6 7 8

1 4 5 6 7 8

2 3 4 5 6 7

2 3 4 5 6 8

2 3 4 5 7 8

2 3 4 6 7 8

2 3 5 6 7 8

2 4 5 6 7 8

3 4 5 6 7 8

>combi 20 20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

この問題は今回の5,6章で学んだ組み合わせや再帰を含む良い問題だと思う。なので、当日はこの問題の自分の答えの発表やid:Nabetaniさんの解説を中心に行った。

*自分の答えは別途掲載します。

id:Nabetaniさんの回答

http://nabetani.sakura.ne.jp/hena/june/を参照

def combi( n, m )
  if m==0 
    yield []
  elsif m<=n
    combi( n-1, m ){ |s| yield s }
    combi( n-1, m-1 ){ |s| yield s+[n] }
  end
end

def combi2( n, m, sel, pos)
  if m==pos
    yield sel
  else
    lo = pos==0 ? 1 : sel[pos-1]+1
    (lo..n).each{ |x|
    sel[ pos ]=x
    combi2( n, m, sel, pos+1 ){ |e| yield e }	}
  end
end
combi( 7, 5 ){ |s| puts s.join(' ') }
puts
combi2( 7, 5, [], 0 ){ |s| puts s.join(' ') }

こちらは桁分ループするスクリプトを動的に生成し、evalする方法

def combi3( v0, m )
  s=(0..(m-1)).map{ |i| "(#{m-i}...v#{i}).each{ |v#{i+1}|" }.join('')
  s+="yield [" + (1..m).map{ |i| "v#{i}" }.join(",") + "]"
  s+="}"*m
  eval s, binding
end
combi3( 6, 3 ){ |v| p v }

で、これが動的に生成したもの

=begin

# combi( 6, 3 )

(3...v0).each{ |v1|

(2...v1).each{ |v2|

(1...v2).each{ |v3|

yield [v1,v2,v3]

}

}

}

=end

これはRubyで作成したcombi2をC++版で実装したもの

#include <vector>
#include <cstdlib>
#include <iostream>

using namespace std;

template< typename proc_type>
void combi( int n, int m, std::vector<int> & sel, int pos, proc_type proc )
{
    if ( m==pos ){
        proc( sel );
    } else {
        int lo = pos==0 ? 1 : sel[pos-1]+1;
        for( int x=lo ; x<=n ; ++x ){
            sel[ pos ]=x;
            combi( n, m, sel, pos+1, proc );
        }
    }
}

void show_vec( vector<int> const & v )
{
    for( int i=0 ; i<v.size() ; ++i ){
        cout << v[i] << " ";
    }
    cout << "\n";
}

int main( int argc, const char * argv[] )
{
    int n = atoi( argv[1] );
    int m = atoi( argv[2] );
    combi( n, m, std::vector<int>(m), 0, show_vec );
}

当日は2グループに分かれてやったので、反対側のグループはというと、なかなか面白そうなのをやっていた。

id:hidecheckさん、Bennettさんの提供問題(ありがとうございます!)

組み合わせ - hidecheckの日記

Androidで3連単フォーメーション馬券 - hidecheckの日記

あと、Bennettさん。

Error 404 (Not Found)!!1 の「B(hidecheckさん・Bennettさんの問題)」あたりを参照。

数学的要素が・・・

濃くなってきた。

# へなちょこレベル99の自分にはハードルが高く感じられるようになってきた

# ある程度の数学プログラミングの素養がないと、この先ついていけなそう…

横浜へなちょこプログラミング勉強会 #3 行ってきました - 謀 跡地

を受けたので、ちょっとやり方を変えてみた。

  • 今回は自己紹介に問題を持参したかを言ってもらって、問題出題者がグループ分けをしたときに偏らないようにした。
  • 出題者を分けた後、参加者自身にどちらのグループでやるかを決めてもらった。

今回はうまいこと分かれたけど、次回はこのやり方でうまくいくかわからない。分け方は再度模索しなくては。

今回初参加のdekiotoさん、kanameさん、nidoさんありがとうございます。

次回7月4日(土)同じ場所、同じ部屋、おんなじ時間です><

よろしくお願いします。

今回の振り返り(グループ分けして、相手が名にやったかわからないので、お互いになにやったか発表中)

Nabetaniさん、cavefishさんは笑い男でごまかし。

f:id:hkhumanoid:20090606201532j:image

これはid:Nabetaniさん作の「渦」。再帰を利用している。

HTML Canvas で 再帰的タートルグラフィックス - 鍋あり谷あり

f:id:hkhumanoid:20090612013735p:image