大文字と小文字の全ての組み合わせを表示

アルゴリズムの基本はソートと探索であると言われることもあります。 大文字と小文字の全ての組み合わせを表示したいのですが・・・では木構造を作って幅優先探索で探すことができます。 キミならどう書く 2.0 - 2007 - その 1 で幅優先探索で求める代表的な問題を私が出題させていただきましたが、キミならどう書く 2.0 - 2007 (その 1) に書かせてもらったものと同じ手法で解くことができます。 つまり、先頭の文字から順に大文字、小文字にしていき、既に一度行き当たったところで探索を終えていくというものです。

#! /usr/bin/gawk -f
# upper_lower.awk
# http://code.nanigac.com/forum/view/422

BEGIN {

    # 引数があれば引数を採用する
    str = ARGV[1] ? ARGV[1] : "test";

    # メイン部
    ul_combi(str);
}

# ul_combi():   大文字小文字の全とおりを出力する
#   in:     文字列
#   out:    大文字小文字の全とおりを出力する
function ul_combi(str) {
    # 区切りを \034 にしてあるものを配列に分割する
    num_arr = split(str, arr, "\034");

    # 文字列の長さ分だけ繰り返すための変数
    i++;

    # 1 文字づつ大文字または小文字変換を行い \034 で連接する
    for (idx in arr) {

        # ダブっていない時だけ追加
        # それ以外は探索打ち切り
        if (uniq_arr[tolower_i(arr[idx], i)] == 0) {
            ul_str = ul_str "\034" tolower_i(arr[idx], i);
            uniq_arr[tolower_i(arr[idx], i)]++;
        }
        if (uniq_arr[toupper_i(arr[idx], i)] == 0) {
            ul_str = ul_str "\034" toupper_i(arr[idx], i);
            uniq_arr[toupper_i(arr[idx], i)]++;
        }

        # 余計な行頭の \034 を削除
        sub(/^\034/, "", ul_str);

    }

    # 全ての文字を変換し終わったら表示する
    if (i >= length(arr[1])) {
        for (idx in uniq_arr) {
            print idx;
        }
    # 残りの文字も大文字小文字変換する
    } else {
        ul_combi(ul_str);
    }
}

# toupper_i():  i 番目の文字を大文字に変換する
#   in:     文字列 str
#   in:     位置 i
#   out:    i 番目の文字を大文字に変換した文字列
function toupper_i(str, i) {
    return substr(str, 1, i - 1) toupper(substr(str, i, 1)) substr(str, i + 1);
}

# tolower_i():  i 番目の文字を小文字に変換する
#   in:     文字列 str
#   in:     位置 i
#   out:    i 番目の文字を小文字に変換した文字列
function tolower_i(str, i) {
    return substr(str, 1, i - 1) tolower(substr(str, i, 1)) substr(str, i + 1);
}

かなり長々としたスクリプトですが、こういう問題は簡単な命令で書き下すことができるため、演習にも最適です。 実際に実行してみます。

$ nawk -f upper_lower.awk
TEsT
TesT
tESt
teSt
TEST
TeST
tEsT
tesT
tEST
teST
TEst
Test
TESt
TeSt
tEst
test

順序がバラバラなのは連想配列である点と途中で探索を打ち切りにしている部分があるからです。 必要に応じてソートすれば良いでしょう。

$ nawk -f upper_lower.awk | sort
TEST
TESt
TEsT
TEst
TeST
TeSt
TesT
Test
tEST
tESt
tEsT
tEst
teST
teSt
tesT
test