スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

perlの再帰プログラミング

Yahoo知恵袋の質問。
すべての組み合わせを求めるプログラムを作成したいです

アルファベット順に従いAから任意の文字数抽出し、それらを並び替えたときのすべての組み合わせを表示するプログラムを作成したいとおもっています。

例えばABCと入力したらそれを並び替えたときのすべての組み合わせ
ABC
ACB
BAC
BCA
CAB
CBA
の6パターン(3!)表示され
ABCDと入力したらそれを並び替えたときのすべての組み合わせ
ABCD
ABDC
ACBD
ACDB

といった具合に24 パターン(4!)が表示される

このようなプログラムです。

perlを使って作成しようと試みています。
具体的なコードというよりは、どのようなアルゴリズムで構築すればよいか
アドバイスをいただけるとうれしいです。
(ここまで)

それに対する私の回答
例えば A B C D の4要素があったとする。これは、次の4種類に分類できる。

(1) Aと、それ以外(すなわちBCD)
(2) Bと、それ以外(すなわちACD)
(3) Cと、それ以外(すなわちABD)
(4) Dと、それ以外(すなわちABC)

ここで、(1)を掘り下げると、次の3種類に分類できる。

(1.1) Aと、Bと、それ以外(すなわちCD)
(1.2) Aと、Cと、それ以外(すなわちBD)
(1.3) Aと、Dと、それ以外(すなわちBC)

さらに、(1.1)を掘り下げると、次の2種類に分類できる。

(1.1.1) Aと、Bと、Cと、それ以外(すなわちD)
(1.1.2) Aと、Bと、Dと、それ以外(すなわちC)

この調子で(4.3.2)まで行うと、結果的に、求める全ての組み合わせができる。

与えられた要素のうちの1つを切り出し、それ以外と分ける。これを与えられた要素分だけ繰り返す。
そして、「それ以外」のうちの1つを切り出し、『それ以外』と分ける。これを「それ以外」のだけ繰り返す。
そして、『それ以外』のうちの1つを切り出し…
…このプロセスを、【それ以外】がたった1つになってしまうまで繰り返す。たった1つになってしまったら、これまで積み上げてきた「1つを切り出し」たものと、たった1つの【それ以外】を並べて表示する。

これを実現するのは、再帰呼び出しを使うのが適しています。
(ここまで)

面白いので、実際に作ってみた。
#!/usr/bin/perl
use strict;

# 処理の都合上、ダミー値を第0要素に挿入してから処理実行
unshift (@ARGV, '');
getCombination (@ARGV);

##########################
# 組み合わせを求める処理
##########################

sub getCombination{
# 要素数が2まで減ったら、これ以上探索できないので
if ($#_ == 1){
# 引き継ぎ分も含め、単純に表示して抜ける
print "@_\n";
return;
}

# 第0要素は、前段から引き継いだ値なので待避
my $PrevBaton = shift (@_);

# 今回処理したい要素分だけループ
foreach my $NextBaton (@_){

# 次段に託したい配列を作成
my @NextArg;
foreach my $tmp (@_){
# 新たに次段へ引き継ぐ値を除いて作成する
$tmp eq $NextBaton or push (@NextArg, $tmp);
}

# 「前段から引き継いだ値+今回の引き継ぎ値」を第0要素として
unshift (@NextArg, "$PrevBaton $NextBaton");

# 次段に託す
getCombination (@NextArg);
}
}


実行結果イメージは以下のとおり。
$ ./recursive.pl A B C D
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A
C A B D
C A D B
C B A D
C B D A
C D A B
C D B A
D A B C
D A C B
D B A C
D B C A
D C A B
D C B A

スポンサーサイト

awkを使った連想配列のようなもの

#!/bin/bash

#----< 値取得関数(引数にキーを与えて呼び出すと、対応する値を返す) >----#
function get
{
awk '/^'$1' /{print $2}' <<_LIST1_
0850467 北海道釧路市阿寒湖温泉(1~6丁目)
0393111 青森県上北郡野辺地町石神裏
1001701 東京都青ヶ島村青ヶ島村一円
7580042 山口県萩市御許町
9042204 沖縄県うるま市西原
_LIST1_
}

#----< メイン処理 >----#
echo "郵便番号7桁を入力せよ"
read YBN
ANS=`get $YBN`

[ $ANS ] || ANS='未登録'
echo $ANS
exit

実行して、郵便番号7桁を入力すると、該当する住所を表示する。
ただし、この例では事前に登録した5つの郵便番号しか対応できない。

こんな勉強をしていこう

  1. パソコンAにApacheを導入し、Webサーバとする。
    パソコンBをAとLANでつなぎ、Bから、ブラウザでAのコンテンツにアクセスする。
    コンテンツは動的なものではなく、ただのHTML紙芝居。
    ここで、B側にHTTP通信内容の確認ツールを導入し、A←→B間でのHTTPのやりとりを確認する。
  2. AのコンテンツにCGIを加える。スクリプトはperlで作成する。
  3. パソコンAにTomcatを導入し、CGIをJava Servlet に変更する。
  4. Java Servlet を JSPに変更する。
  5. DBMSをインストールし、DB接続を試みる。
  6. MVCモデルに基づいてコンテンツを作り直してみる。
  7. 今まではテキストエディタでソースを作成し、コマンドプロンプトからコンパイルしていた。この辺りでeclipseを導入し、開発環境をハイカラにしてみる。
  8. Struts 1 を導入してみる。
  9. Jbossを導入し、EJBを試みる。
  10. 可能であれば、パソコンをもう1台用意し、WebAPサーバとDBサーバを分離してみる。
  11. あるいは、WebサーバとAPサーバを分離してみる。

スマートフォンだ何だと騒がしいこの御時世に、10年も昔に登場した技術をなんで今更、と思われてしまうだろうが、今、自分が保守しているシステムの土台であるJava EE について、基礎からきちんと把握したいのです。
来年3月までに上記がすべてできれば上出来かと思います。
頑張るぞ。

誰かが作ったプログラム 読んで直して15年

私は96年に小規模なソフト会社に就職し、最初の1年間は開発案件に加わっていました。
2年目から保守。汎用機&COBOL。
「ジェットマグロ君、4月から○×社に派遣で保守ね」
と言われたときの暗澹たる気持ちは今でも覚えている。
それでもまぁ、エンジニア人生、時には保守をやってみるのも経験か、と前向きにとらえました。
まさか、その後15年間、ずっと○×社で保守とは夢にも思わずに。

97年~2004年にかけてやっていたのは、基本的に汎用機&COBOL。
扱うのはバッチ処理のみ。DBアクセスはほとんど無しで、ひたすらシーケンシャルファイルを読み書きする。
すべての処理は、「ソート」「マッチング」「キーブレイク」で成り立っている世界。
SQLもほとんど触らなかった。

2004年に、システムの再開発があり、私も1部分、基本設計から携わりました。
「基本設計って楽しいな」
とその時思いました。

2005年以降、新システムの保守にそのまま入る。EJB2.1 + ○×社独自フレームワーク + DB2。
javaに関しては、大学の卒業研究でObjective-Cを扱っていたのですぐにマスターできた。
SQLは必死に覚えた。
今に至るまで、何か不具合が発生する度に、COBOLとjavaで書かれた、誰かが作ったプログラムを、ひたすら読んで直して、その本数はもうとっくに分からなくなりました。

私が最も得意なのは、SQL、シェルスクリプト、awk、excel関数、excelVBA、vbscript などの小技を駆使して、膨大なデータや複雑な形式のログファイルから、必要な情報を扱いやすい形式に整えてチャッチャッと取り出すこと。また、プログラムに不具合が発生し、業務スケジュール上、改修が間に合わない場合に、データに対しチクチクとパッチを当てて、取りあえずエンドユーザの業務が止まらないように一時凌ぎをすること……なんか姑息だ。

レイヤーのかなり上の方、業務ロジックの世界でほとんど勝負しているので、下の方、インフラ面や、JavaEEのアーキテクチャ、DBMSなどに関する知識、技術が弱い。だから、今更ながら、そっち方面を少しずつ勉強して行こうと思っています。
何とか三日坊主にならないように!
プロフィール
カテゴリ
全記事表示リンク

全ての記事を表示する

最新記事
最新コメント
最新トラックバック
月別アーカイブ
RSSリンクの表示
リンク
QRコード
QR
カウンター
にほんブログ村 その他生活ブログ 献血・ドナーカードへ
にほんブログ村
にほんブログ村 その他生活ブログ ボランティアへ
にほんブログ村
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。