2012年2月28日火曜日

再帰について

順列問題を解く

CodeEval より
【問題】
Write a program to print out all the permutations of a string in alphabetical order.

例えば、
hat
という入力に対しては、

aht,ath,hat,hta,tah,tha
と出力する。

順列のような問題は、なんとなく再帰を使うのが良いような気がする。
#! /usr/bin/perl

use strict;
use warnings;

sub perm{
    my @orig_arr = @_;

    if ( scalar(@orig_arr) <= 1 ){
        my $result = shift @orig_arr;
    }
    else {
        my @result = ();
        for (0..scalar( @orig_arr )-1){
            my @workarr = @orig_arr;
            my $top_char = splice( @workarr, $_, 1);

            push @result, map { $top_char.$_ } perm( @workarr );
        }
        @result;
    }
}

sub solve{
    my @result = sort ( perm(split //, shift) );
    foreach (@result){  
        print $_.", ";
    }
    print "\n";
}

solve("hat");

ループでも解けるでしょうか?
再帰でできることは for 文(ループ)でもできるはずなのですが、今回の場合は for 文は意外と難しそう。
何が難しいのかというと "hat" のように 3 文字で固定であれば 2 つの for 文のネストでできますが、 文字数は可変なので静的なプログラムが書けない(と思う)。 for 文を結局再帰したくなる・・・。
そこで、新しい発見かもしれない教訓、

”繰り返し数が固定でない場合は、再帰処理が有効”


再帰は危険

for 文で書くのに何かヒントは無いかと、Code Complete を紐解いてみる。 「再帰を使って行えることは全て、スタックと繰り返しを使って行うことができる」とある。
そうかスタックね。・・・でもわからん。この問題はしばらく寝かせよう・・・。

ところで、前述の本には「再帰の使用に関するヒント」という項目に有用なヒントが幾つかあって、最後に「階乗やフィボナッチ数列に再帰を使用しない」とある。
そして、再帰は遅くて、消費メモリの予測ができなくて、理解が難しいと説明してあり、さらにかなり強い調子で「仮に、私の部下が再帰を使って階乗を計算しようものなら、別の誰かを雇うだろう」といっている。
上司によっては職を失いかねない危険をはらんでいます。再帰を使うときは要注意っと。






2012年2月5日日曜日

Mac の Finder で上の階層に移動したい

Mac の Finder で、今表示されているフォルダの上の階層へ移動する方法のメモ。
(キーバインドは、Command + ↑)
そして、メモしようと思って画面のキャプチャをしたときに色々と知ったことのメモ。

Finder で上の階層へ移動
Mac の Finder で自分のホームディレクトリー /Users/xxx を見たいときに Finder を起動すると、以下のような画面が開きます。
Windows のエクスプローラーのようにフォルダをたどって探したいのですが少し勝手が違います。
アイコンが並んでいる隣のサイドバーを見ても /Users などという名前もないし、画面上のボタンを押しても、/Users へたどっていけません。

ここで、キーボード操作で ' Command + ↑ ' とすれば一つ上の階層に移動できます。
(そして、下図の場合では「ユーザ」が /Users に相当するのでそこからたどれば /Users/xxx が見られる。)
上の階層の最後まで行くと、' Macintosh HD ' までたどれます。ココまで来ればアイコンダブルクリックで希望の下の階層へたどれます。
単に' Macintosh HD ' へ移動したい場合は ' Shift + Command + C ' で、一発で出来ました。C は「コンピュータ」の C 。
(メニューの「移動」にありました。)

しかし、上記のキーバインドは多分忘れるので、サイドバーに ' Macintosh HD ' を登録しておきます。' Macintosh HD 'アイコンを選択した状態で「ファイル」→「サイドバーに追加」。


サイドバーの一番下に ' Macintosh HD ' が追加されました。

画面のキャプチャについて
本題とは関係ないですが、記事を書くのに画面のキャプチャをやって、これも覚えておいたほうがよさそうなのでメモ。

あるウィンドウをキャプチャするのは、' Command + Shift + 4 + Space ' を押して、出てきたカメラアイコンでウィンドウを選択する。
(' Command + Shift + 4 ' は片手で押すには無理があるので、今度やるときは4は右手にする。)

今回メニューをキャプチャしようとしたら、下図のように思っていたのと違う画面が取れてしまった。
「 Dock に追加 」は本当は「サイドバーに追加」。

キャプチャする時に ' Shift ' キーを押してしまうのでメニューの内容が変わってしまうのです。


別のキャプチャの方法を探したら、「グラブ」というソフトがありました。「アプリケーション」→「ユーティリティ」から起動。
Shift キーを押さずに10秒タイマーでキャプチャできます。









その他
Finder の「デバイス」に FireFox があるのが気になりますが、話が発散しすぎるのでスルー。