Problem 118

R Project Euler

1 から 9 の全ての数字を使い、自由につなげることで 10 進数の数字を作り、複数の集合を作ることができる。集合 {2,5,47,89,631} は面白いことに全ての要素が素数である。
1 から 9 の数字をちょうど 1 個ずつ含み、素数の要素しか含まない集合はいくつあるか?

見るからに組み合わせが爆発しそうな問題．並び替え×分割パターンなのでそれはそれは大変なことに．
どうにかこうにか調べる組み合わせを減らして30秒．Rの割によく頑張ったと思う．でも多分まだもうちょっと短縮できる．
今回はgmpの他にcombinatパッケージを使った．順列を列挙するpermn関数などが使えるのでこれもPE進めるのに便利なパッケージだ．

library(combinat)
library(gmp)

v2dig <- function(v) as.numeric(paste(v, collapse=""))
permn2dig <- function(x){
  if(length(x) == 1) return(x)
  unlist(lapply(permn(x), v2dig))
}
  
f <- function(d, last = 0){
  n <- length(d)
  if(n <= 2) return(0)
  ans <- 0
  for(i in 1:(n/2)){
    subs <- combn(d, i)
    coln <- ifelse(i == n/2, ncol(subs)/2, ncol(subs))
    for(j in 1:coln){
      if(last >= v2dig(subs[, j])) next # 小さいものは先に調べているはず
      t <- sum(isprime(permn2dig(subs[, j])) != 0)
      if(t == 0) next
      nextd <- setdiff(d, subs[, j])
      last <- v2dig(subs[, j])
      ans <- ans + t * (sum(isprime(permn2dig(nextd)) != 0) + 
                        Recall(nextd, last))
    }
  }
  return(ans)
}

system.time(f(1:9))