Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
順列とはモノの順番付きの並びのことである. たとえば, 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.辞書式に並べるとはつまり昇順に並べることである。
2.次に、例えば1桁目を0と仮定すると$9!=362880$通り存在する。
3.$1000000/362880=2 あまり274240$であるから、
1桁目が0と1の場合は全て収まりきり、1桁目が2のときに100万桁目に到達する。
よって、1桁目の値は$2$に決まる。
4.これを繰り返していく。
5.7桁目まで決まると余り4になる。
$4=2*2$であるので8桁目は残っている数字で2番目に大きい数、9桁目も2番目に大きい数になる。
(6.ロジック的に10桁目は「残っている数字で1番大きな数」とする。たまたま0だが。)
解答
seq 9 |
tac |
awk '{a=1;for(i=1;i<=$1;i++){a*=i};print a,11-i}' |
awk 'BEGIN{n=10^6} {s=int(n/$1);n=n%$1;print s,n,$0}' |
sed '/^0 /d' |
awk '$2!=0{print $1+1,$2,$3,$4} $2==0{v[1]=$1;v[2]=$3;v[3]=1;for(i=$4;i<=10;i++){print v[i-7],$2,$3,i}}' |
awk '{c=0;for(i=0;i<=9;i++){if(!(i in a)){c++};if(c==$1){break}};a[i]=1;printf i}'
2783915460
他の番目ではできないかも。
ひとまず余りが4になるような番目なら可。
疲れたからこの問題もうやりたくない。。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/024.html