パスカルの三角形を計算するBashワンライナー

Last updated at 2019-12-21Posted at 2019-12-21

実行結果

パスカルの三角形を計算するワンライナー

eval echo "1" "| awk '{print \$0}END{printf \"1 \"; for (i=1; i<NF; i++) {printf \"%s \", \$i+\$(i+1)} print \"1\"}'"{,,,,,,,,,}

実行結果

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

解説

このコードの肝となっているのが、ブレース展開というBashが持つ機能です。
ブレース展開とは、例えば次のようなものです。

ブレース展開の例

echo "test"{1..10}
#> test1 test2 test3 test4 test5 test6 test7 test8 test9 test10
echo {,k,s,t,n,h,m,y,r,w}a
#> a ka sa ta na ha ma ya ra wa

{n..m}(n,mは自然数)とすると、このブレースはコマンド実行時にnからmまでの自然数の数列に展開され、2つの目の例のようにコンマ区切りで要素を並べたものはそれら要素を半角スペースでつなげた文字列に展開されます。
さらにこのブレースの前後に文字列をくっつけると、数学の世界で$a(m+n)$が$a×m+a×n$になる分配法則のように、文字列が展開されます。

ところでコンマ区切りで並べた要素は二つ目の例で見たように、空の文字列でも構いません。例えば、

echo "yes"{,,,,,,}
#> yes yes yes yes yes yes yes

というようになります。

このことを利用すると同じ文字列をコンマの数+1ぶん作ることができます。

パスカルの三角形の計算方法はいくつかありますが、一番初歩的なのは隣接する項同士の和を頂点から順々に計算していくという方法でしょう。この計算をawkで書いたものが次のコードです。

各段の計算

awk '{
    printf "1 ";
    for (i=1; i<NF; i++) {
        printf "%s ", $i+$(i+1);
    }
    print "1"
}'


#例えば…

echo "1 2 1" | awk '{上に同じ}'
#> 1 3 3 1
echo "1 2 1" | awk '{上に同じ}' | awk '{上に同じ}'
#> 1 4 6 4 1
echo "1 2 1" | awk '{上に同じ}' | awk '{上に同じ}' | awk '{上に同じ}'
#> 1 5 10 10 5 1

すなわちこのawkのコードをm回適用するとパスカルの三角形のm段目の数値が計算できるというわけです。

ただ、何回も同じコードを書くのはあまりきれいじゃないですし、コピペするのも大変ですからここで先程お話ししたブレース展開を用います。

つまり、

(1)

echo "1 2 1" | awk '{上に同じ}' | awk '{上に同じ}' | awk '{上に同じ}' | awk '{上に同じ}'

と書いていたものを

(2)

echo "1 2 1" " | awk '{上に同じ}'"{,,,}

と書いて、"コマンド"{,,,}の部分をBashによって展開してもらおうという話です。

さて、この部分を展開する方法はいくつかあるのですが、いちばんスッキリと書けるのはevalコマンドを用いる方法です。evalもBashの機能の一つですが、このコマンドに文字列を食わせるとコマンドとして実行できる部分やブレース展開のように展開できる部分を展開してくれます。

たとえば、

(3)

eval echo "1 2 1" " | awk '{上に同じ}'"{,,,}

といったコードを実行すると、まずevalコマンドによりeval以降の文字列(すなわち$(2)$)が評価され、$(1)$のコードが返り、それがBashによって解釈され実行されます。

このようにブレース展開をうまく駆使すると、最初に掲げたようなワンライナーでパスカルの三角形をシェル上に表示させることができます。

Bash上で再帰的な計算や何回も同じ関数を適用するような計算を行ないたいときに、eval "コマンド列"{,,,}というイディオムを覚えておくといつか役に立つときがあるかもしれません(笑)。

パスカルの三角形を計算するBashワンライナー

実行結果

解説

関連記事・参考リンク