部分和問題を解くアルゴリズムをプログラミングしてみる
部分和問題
ちょうど部分和問題について触れることがあったので，久しぶりにプログラミングの練習．
部分和問題とは，
与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題
という問題．(部分和問題 - Wikipediaより)
例えば，{1,2,3,4,5,6}のうちいくつかを足して21にできるかどうか，という問題．
これを解くアルゴリズムとして，
- {1,2,3,4,5,6}の一つ一つについて選ぶか選ばないかを決め，
- そのそれぞれの選び方で選んだ数の和のうち，21になるものがあればYESと判定
- 一つも21になるものがなければNOと判定
を採用．
選ぶか選ばないか2通りの選択が，{1,2,3,4,5,6,7}の集合の要素数分だけあるから，
要素数が増えれば計算量は指数関数的に増えていく．．．
PHPでプログラミング
整数の集合は配列(変数$S)で，与えられた数は変数$tで宣言．
まずはアルゴリズムの通りに実装したいので，再帰関数を使用．
集合から一つ数を取り出して，その数を選ぶ場合と選ばない場合に再帰を用いて分岐．
選ぶ数は別の配列に保存して，集合が空になったときに選んだ数を足し合わせて判定．
<?php $S = array(1, 2, 3, 4, 5); $t = 21; bubun($S, array()); print "NO\n"; function bubun($S, $a){ global $t; if(empty($S)){ $i = array_sum($a); if($i == $t){ var_dump($a); exit(); } }else{ $i = array_pop($S); bubun($S, $a); array_push($a, $i); bubun($S, $a); } } ?>
問題としては，選んだ数を表示しなくてもいいから(判定するだけでよい)，
変数$tから値を引く・引かないで選ぶ・選ばないを分岐させて，
<?php $S = array(1, 2, 3, 4, 5, 6); $t = 21; bubun($S, $t); print "NO\n"; function bubun($S, $t){ if($t == 0){ print "YES\n"; exit(); }elseif(empty($S)){ return; } $i = array_pop($S); bubun($S, $t); bubun($S, $t-$i); } ?>
再帰ではなくて，繰り返しでできないか，ということで，，
新たに，足し合わせた数を格納する配列を用意して，
- 集合から一つずつ値を取り出す
- 配列をコピー
- 一方には取り出した値を足し合わせる
- 配列をくっつける
という感じで，足す・足さないで選ぶ・選ばないを実現
<?php $S = array(1, 2, 3, 4, 5, 6, 7); $t = 21; $sum = array(); for($temp = $S; !empty($S); $temp = $sum){ $a = array_pop($S); for($i=0; $i<count($sum); $i++) $sum[$i] = $sum[$i] + $a; $sum = array_merge($sum, $temp); } array_search($t, $sum) ? print "YES\n": print "NO\n"; ?>
SQLで実現
部分和問題でググってたら，SQLで解くという話がおもしろかった．
サービス終了のお知らせ - Yahoo!ジオシティーズ
http://d.hatena.ne.jp/kano-e/20070809/1186672517
CやPHPと違って構造化プログラミングができないから，解くのが難しい．
上記のリンクのkano-e no memoさんの方法が一番良いんじゃないかと．
- 0と1が入ったbool表を用意
- bool表を集合の要素回だけ結合(直積して要素数桁のすべてのビットパターンを生成)
- 1が現れた場所に各要素を外部結合
- 選んだ要素を足し合わせて，目的の行を選択
って感じかな．
外部結合部分で少し削れそうな部分があったので，いじってみる．
集合の各要素はSQL文の中に書いちゃって，それを保存しておくテーブルはいらなくなるかも．
SELECT n1, n2, n3, n4, n5 FROM ( SELECT a, b, c, d, e, coalesce(n1.id, 0) n1, coalesce(n2.id, 0) n2, coalesce(n3.id, 0) n3, coalesce(n4.id, 0) n4, coalesce(n5.id, 0) n5 FROM ( SELECT a.id a, b.id b, c.id c, d.id d, e.id e FROM bool a, bool b, bool c, bool d, bool e ) as f LEFT JOIN ( SELECT 1 id ) as n1 ON a = 1 LEFT JOIN ( SELECT 2 id ) as n2 ON b = 1 LEFT JOIN ( SELECT 3 id ) as n3 ON c = 1 LEFT JOIN ( SELECT 4 id ) as n4 ON d = 1 LEFT JOIN ( SELECT 5 id ) as n5 ON e = 1 ) as ssp WHERE n1 + n2 + n3 + n4 + n5 = 7 ;
インストール後
再起動すると自動的にfedora10が起動するようになった．
とりあえずアプリケーションの更新等をしてfedora側はOK.
起動時にpress any key...の画面でキーを押すとOSの選択画面が現れて，Otherを選択するとVistaが起動．
fedora10インストール後の最初のVistaの起動時に，黒い画面が現れてシステムのチェックをしているという旨のメッセージが表示される．
そのまま放置してたら再起動されて，またVistaを選択して起動．
Vistaのデスクトップが表示されると，デバイスドライバをインストールしているという旨のメッセージが表示される．
そのインストール後再起動して，次から普通にVistaもfedora10も使えた．
めでたしめでたし．
インストール
まずはfedora10のLiveCDを挿入して起動する．
Install to Hard Drive を起動してインストーラが起動する．
キーボードの設定，Japaneseを選択する．
コンピュータの名前の設定，かまわない．
rootのパスワードを設定．
次がデュアルブート用の設定．
インストール先のパーティションの選択で，Resize existing partition ・・・(パーティションのサイズを変えて空きスペースを作る)を選択
下はVistaが入っているsda(Cドライブ)のままにしておく．
Nextを押したらCドライブをどれだけのサイズに変更するか聞いてくるので，てきとーに40000MB減らしてみる．
確認，，怖いw
Write changes to disk で処理が進んで，，，
インストール完了．
Vistaにfedora10をインストールしてみた
先日VistaがインストールされたノートPCを購入した．
http://itpro.nikkeibp.co.jp/article/NEWS/20080207/293253/ によると，
fedora9からデュアルブート環境を作りやすくなったというので，fedora10をインストールしたのでメモ．
アルゴリズム/CSVファイルデータの読み込み
CSVファイルのデータを扱いたい。
でも「,」を含む値も取り扱いたい。。。ということがあったのでメモです。。。
CSVの仕様によると、
とのことなので、(参考/RFC4180 http://www.ietf.org/rfc/rfc4180.txt)
ダブルクォートのエスケープが面倒くさいけど
「,」を含むデータを取り扱うにはダブルクォートで囲めばよいそうです。
今回は、ダブルクォート内に改行が含まれない1行のCSVデータを読み込み、各値を配列で返す処理を考えます。
簡単に考えるために1行の文字を先頭から見ていき、遷移する状態として次の5状態を考えます
- 初期状態
- 各データ先頭文字の状態、データ状態のいずれかへ遷移
- データ状態(非クォート)
- ダブルクォートで囲まれない場合で、コンマが現れるまでデータとして取り込んで行く
- データ状態(クォート)
- ダブルクォートで囲まれている場合、ダブルクォートが現れるまでデータとして取り込んで行く
- ダブルクォート中のダブルクォート状態
- 次の文字がダブルクォートなら再びクォート内のデータ状態へ移り、コンマならデータ末尾
- データ末尾状態
- 各データの末尾まで読み込んだ状態で、配列に詰め込む
以上の状態遷移をもとにPHPで記述してみました。
<?php function csv($dataline){ $result = array(); $len = strlen($dataline); //各状態の初期化 // start, not_quoted, quoted, end_or_escape, end $state = "start"; $tmp = ""; for($i=0; $i<$len; $i++){ $ch = $dataline[$i]; switch($state){ case 'start'://初期状態の処理 if($ch == '"') $state = 'quoted'; elseif($ch == ',') $state = 'end'; else { $state = 'not_quoted'; $tmp .= $ch; } break; case 'not_quoted'://クォーティングされてない場合 if($ch == ',') $state = 'end'; else $tmp .= $ch; break; case 'quoted'://クォーティングされている場合 if($ch == '"') $state = 'end_or_escape'; else $tmp .= $ch; break; case 'end_or_escape'://クォーティング中のクォート if($ch == '"'){ $state = 'quoted'; $tmp .= '"'; } else $state = 'end'; break; } if($state == 'end'){ $state = 'start'; $result[] = $tmp; $tmp = ""; } } //最後の要素を結果に詰め込む //行末がコンマで終わる時はデータとして含めない if($tmp != "") $result[] = $tmp; return $result; } ?>
状態遷移の仕方などよく考えるともっとコードは短くなりそうです。
Fedora7/sensorsを動かす
sensorsを動かすためにsensors-detectコマンドを実行
途中で現れる選択肢にはすべてyesで対応
# sensors-detect
# sensors-detect revision 4609 (2007-07-14 09:28:39 -0700)
This program will help you determine which kernel modules you need
to load to use lm_sensors most effectively. It is generally safe
and recommended to accept the default answers to all questions,
unless you know what you're doing.(中略)
To make the sensors modules behave correctly, add these lines to
/etc/modprobe.conf:#----cut here----
# I2C module options
alias char-major-89 i2c-dev
#----cut here----To load everything that is needed, add this to some /etc/rc* file:
#----cut here----
# Chip drivers
modprobe w83627ehf
modprobe coretemp
# sleep 2 # optional
/usr/bin/sensors -s # recommended
#----cut here----If you have some drivers built into your kernel, the list above will
contain too many modules. Skip the appropriate ones! You really
should try these commands right now to make sure everything is
working properly. Monitoring programs won't work until the needed
modules are loaded.Do you want to overwrite /etc/sysconfig/lm_sensors? (YES/no): yes
あとは(中略)後の指示に従うだけ。
/etc/modprobe.confの末尾に
#----cut here----
# I2C module options
alias char-major-89 i2c-dev
#----cut here----
を追加。
次に/etc/rc.d/init.d/へ移動し、
#----cut here----
# Chip drivers
modprobe w83627ehf
modprobe coretemp
# sleep 2 # optional
/usr/bin/sensors -s # recommended
#----cut here----
を記述したシェルスクリプトファイルを作成。
あとはln -sコマンドでシンボリックリンクを/etc/rc.d/rc5.d/ディレクトリに作成。
これでsensorsコマンドを使用できるようになりました。
