Project Euler Problem 24 - 順列の辞書順ソート

Problem 24 - Project Euler

順列とは要素の並び替えのことである。たとえば3124は数字1, 2, 3, 4の並び替えで得られる順列の一つだ。全ての順列をアルファベット順またはABC順に並び替えたとして、それを辞書順と呼ぶことにする。0, 1, 2の順列を辞書順に並び替えたとすると、結果は

012 021 102 120 201 210

となる。0, 1, 2, 3, 4, 5, 6, 7, 8, 9の順列を辞書順に並び替えたときの100万番目は何か。

以下解答。

そのままやると終わらないが、1桁減らしてやると11秒で終わる。9桁使った場合に可能な順列はfactorial(9)=362880通りなので、最上位桁は2であるとわかる。

combn()の順列版であるpermn()がcombinatパッケージに入っているので、それを使うとこんな感じでいける。

sort(sapply(combinat::permn((0:9)[-3]), paste0, collapse=""))[1e6 - factorial(9)*2]

ところで、n桁使った場合に可能な順列がfactorial(n)通りであることは明らかなので、そもそも順列を実際に作って調べる必要はない。

limit = 1e6
cnt = 1
digits = as.character(0:9)
digp = 1
rest = 9 
ans = character(0)

while(rest > 0){
  if(limit >= cnt + factorial(rest)){
    cnt = cnt + factorial(rest)
    digp = digp + 1
  } else {
    rest = rest - 1
    ans = c(ans, digits[digp])
    digits = digits[-digp]
    digp = 1
  }
}

13ms。