攪乱順列

https://codeiq.jp/q/2636

銀行のATMなどで暗証番号を入力するときに使用するテンキー。
覗き見られたときのセキュリティを意識して、配置がランダムに変わる機種もあります。
今回はすべてのキーが元の配置とは異なる位置に配置することになりました。
そこで、このような配置が何通りあるかを求めるように依頼されました。

ビット演算だとかメモ化だとか再帰プログラムとかいっている。

「メモ化の練習」と言っているのだからまあよいが，そんなもん，公式があるんだから，瞬殺。

http://mathtrain.jp/montmort

これに限らないが，なんでもプログラムでやろうとするのは止めといた方がよい。

> func = function(n) factorial(n) * sum((-1)^(2:n) / factorial(2:n)) # 一行野郎

> system.time(print(func(10)))
[1] 1334961
   ユーザ   システム       経過  
         0          0          0
> system.time(print(func(12)))
[1] 176214841
   ユーザ   システム       経過  
         0          0          0

n = 18 までは正しい答えが得られる

gawk で --bignumオプションを使って最適化すると，無制限

$ cat b.awk
{
  n = $1
  sign = s = n % 2 == 0 ? 1 : -1
  p = 1
  for (i = n; i >= 3; i--) {
    p = p*i
    sign = -sign
    s = s + sign * p
  }
  printf "%i\n", s
}

$ echo 10 | gawk --bignum --file=b.awk
1334961

$ echo 12 | gawk --bignum --file=b.awk
176214841

$ echo 100 | gawk --bignum --file=b.awk
34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601

$ echo 101 | gawk --bignum --file=b.awk
3467612394400544281284793730204390345268944164342954283337883428551203260126090875711931039414949888013971937935734182467628150127669980115929442267844057738700