Project Eulerをシェル芸で解いてみる(Problem 24) #シェル芸

概要

Project Euler¹は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸²による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。

本記事では、Project EulerのProblem 24を、シェル芸で解いた際の過程を述べる。

実行環境

• Arch Linux (x86_64, 4.3.3-3-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

[原文 (https://projecteuler.net/problem=24)]

Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012\ \ \ 021\ \ \ 102\ \ \ 120\ \ \ 201\ \ \ 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2024)]

辞書式順列

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012\ \ \ 021\ \ \ 102\ \ \ 120\ \ \ 201\ \ \ 210

になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

正答は、注釈³に記載する。

解法

1   #!/bin/sh
2   
3   (seq -s ' ' 0 9; echo 1000000) \
4   | # 順列と番数の生成
5   sed -e '1h; 2p; 2g' \
6   | # 順列の複製
7   awk 'NR != 3; NR == 3 {ORS=""; for(i=1; i<NF; i++){print i " "}; print "\n"}' \
8   | # 複製した順列の各要素について、(要素順序-1)に変換
9   awk 'NR != 3; NR == 3 {for(i=NF; 1<=i; i--){p=1; for(j=$i; 1<j; j--){p*=j}; print p}}' \
10  | # (要素順序-1)について、それぞれ(要素順序-1)!の出力
11  awk 'NR == 1; NR == 2 {n=$0-1} 3 <= NR {i=1; while($0*i <= n){i++}; print i--; n=n-$0*i}' \
12  | # 順列から要素を取り出す順序の算出
13  awk '
14      NR == 1 {for(i=1; i<=NF; i++){n[i]=$i}}
15      2 <= NR {ORS=""; for(i=1; i<=$0; i++){$0+=(n[i] == "f") ? 1 : 0} print n[$0] "\n"; n[$0]="f"}
16      END {for(i in n){print (n[i] != "f") ? n[i] : ""}}
17      ' \
18  | # 番数に該当する数値の生成
19  xargs \
20  | # 行->列変換
21  tr -d ' '
22    # 出力の整形

以下、コマンドライン上での実行用コードである。

(seq -s ' ' 0 9; echo 1000000) | sed -e '1h; 2p; 2g' | awk 'NR != 3; NR == 3 {ORS=""; for(i=1; i<NF; i++){print i " "}; print "\n"}' | awk 'NR != 3; NR == 3 {for(i=NF; 1<=i; i--){p=1; for(j=$i; 1<j; j--){p*=j}; print p}}' | awk 'NR == 1; NR == 2 {n=$0-1} 3 <= NR {i=1; while($0*i <= n){i++}; print i--; n=n-$0*i}' | awk 'NR == 1 {for(i=1; i<=NF; i++){n[i]=$i}} 2 <= NR {ORS=""; for(i=1; i<=$0; i++){$0+=(n[i] == "f") ? 1 : 0} print n[$0] "\n"; n[$0]="f"} END {for(i in n){print (n[i] != "f") ? n[i] : ""}}' | xargs | tr -d ' '

解説

まず、解答方針を述べる。

辞書式順列の各要素は、階乗の組合せによって表現できる性質を利用する。(参考1)

要素数$i$の順列$P$が存在するとする。
この順列$P$について、要素を辞書順に並べた場合、$n$番目の値は、以下の数式で表すことができる。

n = a(i-1)! + b(i-2)! + ... + z(i-(i-1))! + 1 \cdot 0! \hspace{3em} \text{(a, b, ..., zは定数)}

ここで、定数$a, b, ..., z$について、それぞれ$1$を足し合わせ、数列$a+1, b+1, ..., z+1$を得る。
次に、数列"a+1, b+1, ..., z+1"を先頭から順に参照していき、元の順列$P$について、数列の数値に対応する番号の要素を取り出していく。
そして、取り出した要素を順番に並べると、$n$番目の値となる。

具体例として、要素数3の順列、"0, 1, 2"の場合について考える。
順列"0, 1, 2"を辞書順に列挙すると、以下の6つの数値が得られる。

1: 012 \\
2: 021 \\
3: 102 \\
4: 120 \\
5: 201 \\
6: 210

階乗を用いると、上記の行番号(数値の順番)は次のように変形できる。

1 = 0 \cdot (3-1)! + 0 \cdot (2-1)! + 1 \cdot 0! \\
2 = 0 \cdot (3-1)! + 1 \cdot (2-1)! + 1 \cdot 0! \\
3 = 1 \cdot (3-1)! + 0 \cdot (2-1)! + 1 \cdot 0! \\
4 = 1 \cdot (3-1)! + 1 \cdot (2-1)! + 1 \cdot 0! \\
5 = 2 \cdot (3-1)! + 0 \cdot (2-1)! + 1 \cdot 0! \\
6 = 2 \cdot (3-1)! + 1 \cdot (2-1)! + 1 \cdot 0!

ここで、階乗にかかる係数に注目する。
例えば、$4$の場合、係数は先頭から順に、"1, 1, 1"である。
この得られた順列の、$0!$の係数を除いた全要素に対して、それぞれ$+1$すると、"2, 2, 1"が得られる。

次に、先ほど得られた順列の各要素の数値について、元の数列"0, 1, 2"の要素番号に対応した要素を取り出していく。
まず、"0, 1, 2"から、要素番号$2$に対応した要素を取り出す。
この場合、対応する要素は$2$である。

0, 1, 2
- -
0, 1, 2
1

同様にして、残った順列"0, 2"から、要素番号$2$に対応した要素を取り出す。

0, 1, 2
- -
0, 1, 2
12

最後に、順列"0"から、要素番号$1$に対応した要素を取り出す。
(この場合、$0$であることは自明である。)

0, 1, 2
120

以上の操作によって、辞書順4番目の数値である、$120$を求めることが出来た。
今回の解法では、上記の手順を実装すれば良い。

---

次に、ソースコードの解説を述べる。

まず、設問で定義されている順列"0, 1, 2, 3, 4, 5, 6, 7, 8, 9"と、要求されている番号$1000000$を生成する。
この処理は、3行目のseqとechoを用いておこなう。
サブシェル上で実行することにより、両コマンドの出力をパイプラインへと入力している。

次に、求める$1000000$番目の数値を階乗で表した際の、階乗にかかる各係数を求める
この処理は、5~11行目のsed、awkを用いておこなう。
まず、係数を求める下準備として、5行目のsedを用いて、順列を複製する。
次に、7行目のawkを用いて、複製した順列から階乗の基数を生成する。
そして、9行目のawkを用いて、それぞれの基数について階乗を出力する。
最後に、11行目のawkにて、階乗の係数を求めていく。
ここでは、それぞれの階乗について、数値$1000000-1 - (直前までの階乗の総和)$を超えない範囲を探索することで、係数を求めている。
また、数値$1000000$から$1$を引いている理由は、$0!$の係数である$1$の存在を考慮したためである。

そして、順列"0..9"から、係数に対応した要素を取り出していく。
この処理は、13~17行目のawkを用いておこなう。
具体的には、今まで加工せずに出力していた1行目の順列を配列化し、係数の番号に対応した値を取り出している。
この時、一度値を取り出した配列は、次回以降の探索から除外するため、取り出した値の代わりにフラグを代入している。

最後に、取り出した値を数値の形に整形する。
この処理は、19~21行目のxargs、trを用いておこなう。

以上が、0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目の数値を求める方法である。

参考にしたもの

1. "特定の順列を見つける方法" 〈http://www004.upp.so-net.ne.jp/s_honma/urawaza/permutation.htm〉

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺

• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
  
  

• 辞書式順列には、階乗に関連した規則性があることは発見できたけれど、その規則性を上手くアルゴリズム化出来なかった...

  • という理由で、解法をググってしまったorz
  • まだまだ修行が足りぬ...(¦3_ヽ)_

• 階乗にかかる係数に$+1$しているけれど、一般的なプログラミングの配列では、$+1$しないで考えたほうが、やりやすいかも。

• 今回の解法、何だかawkで反復処理ばかりしていて、シェル芸以外のコードとあまり変わらない気がする...

  • 解法を考える段階で苦労した割には、何だかコードに面白味が無いというか。

• そもそも、何故今回の解法で辞書式順列の値が算出できるのか、詳細な仕組みがよく分からない...

  • 余力(主に脳味噌に)があれば、そういった数学的な仕組みも調べてみたいな...

---

---

1. About - Project Euler (https://projecteuler.net) ↩

2. シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩

3. 2783915460 ↩