2016年1月30日土曜日

プロジェクトオイラー 問118

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。


問118「パンデジタル素数集合」
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる.
集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.

1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?



注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。




私の回答例は以下の通りです。
def h(n):
 if n<2: return 0
 if n<4: return n
 if (not n%2): return 0
 for i in xrange(3, int(n**.5)+1, 2):
  if not n%i: return 0
 return n

def f(L, Lc=[], d=0, cnt=0):
 if d==9:
  return [], cnt+1
 bk = Lc[:]
 for i in xrange(len(L)):
  Lc = bk[:]
  s = 0
  for j in L[i:]: s = s*10 + j

  if Lc and Lc[0]<s: continue
  if h(s):
   Lc.insert(0, s)
   Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
  return Lc, cnt

import itertools
L0 = [i for i in xrange(1, 10)]
v = 0
for t in itertools.permutations(L0):
 L, c = f(t)
 v += c
print "cnt:", v

1から9までの数字の順列を発生させ、その1つひとつについて、素数だけの要素に分解していきます。
ただし、その分解できた要素の順番が異なっていても1つとして数えるため、要素が昇順に並んでいるパターンだけの件数を数えます。
総当たりですが1分ルールは守れるのでよしとします。


1.関数f(n)
・リストLの要素を左から素数で区切り、累積用リストLcに格納していきます。
 dは確定した全要素の合計桁数で、cntは全素数要素のパターン数です。
 最終的に必要な値は件数だけですが、この関数を回帰呼び出しで使えるようにするために、戻り値は累積用リストLcと求める件数とします。


・回帰呼び出しなので、最初は終了条件の記述が鉄則です。
 確定した全要素の合計桁数が9ならば、1~9の数字の全部を使い切っていて、累積用リストLcに求めるパターンが格納されているので、空の累積用リストとカウンタcntを+1して戻ります。


・累積用リストLcのバックアップを取ります。
 左から1桁ずつ区切って要素を確定していく中で、区切り方が条件に合わない場合に直前状態に戻すためです。


・for j in L[i:]: s = s*10 + j
 位置iから右側を切り取り L[i:]とし、
 jのforループ中で、1けたずつ取り出して10倍しながら足していき数値化しsとします。


・if Lc and Lc[0]<s: continue
 重複を避けるため、全要素が昇順になる場合だけ採用し、それ以外は次へ。


・if h(s):
  Lc.insert(0, s)
  Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
 関数hで数値sの素数判定します。
 素数ならば、累積用リストLcに右から追加します。
 そしてリストLの位置iから左側L[:i]について、当関数fを再起呼び出しして、さらに素数の要素があるか探索します。
  
2.関数h(n)
問111の素数判定を改良しました。
 2未満に素数は無く、2と3は素数。ここまではif文で直接判定します。
 その後は偶数を外し、3から先の奇数の倍数を外します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
44680