3

質問：整数を反復処理してその中の他の整数を見つけ、それらが含まれている場合はその整数を破棄するための最良の方法は何ですか？

ロングバージョン：

私は、プロジェクトオイラーの問題を効率的に解決するために、Pythonのスキルに取り組んできました。約20の問題を経験した後、問題を解決することはできますが、私の解決策はしばしばエレガントで不格好です（つまり、醜くて遅い）。問題が構造化されている方法では、より複雑なものがこれらの非効率性を悪化させるので、私はいくつかのより良い解決策を学ぶ必要があると思います。

とにかく、今日私は問題35に取り組んでいます。これは、1,000,000未満のすべての循環素数を要求します。1,000,000未満のすべての素数のリストを作成し、以下の素数の順列を吐き出すための小さなフレームワークを作成しました。それぞれについて、素数のテストを計画していました。

def number_switcher(number):
  number = [num for num in str(number)]
  numlist = [''.join(num) for num in list(itertools.permutations(number))]
  return [int(num) for num in numlist]

これをすべての素数で実行してから、考えられる各順列の素数をテストすることは、ご想像のとおり、問題を解決する方法ではありません。

次に、順列の実行を開始する前に、偶数を含むすべての数値（1桁より長いと仮定）または5を含む任意の数値を破棄できることに気付きました。

これが私が本当に迷子になった場所です。簡単そうに見えますが、2日間試してみたら、偶数や5が入った複数桁の数字を捨てる方法がわかりません。

これが私が試したものです（ここで「素数」と呼ばれる1,000,000未満のすべての素数のリストを想定しています）：

 [num for num in primes if any(x for x in '024685' in str(num))] # failed: 'bool' object is not iterable

次に、次のことを試しました。

for prime in primes:
  if '0' in str(prime):
    primes.remove(prime)

>>>>len(primes)
4264

これにより、素数リストが約半分になりました。さて、おそらく私は正しい方向に進んでおり、「str（prime）の「0」またはstr（prime）の「2」の場合」などの醜いものが必要です。

しかし、ここに奇妙なことがあります。「素数」リストを調べると、まだ「0」が含まれている素数が含まれています。新しい素数のリストで同じことをもう一度実行すると、次の結果が得られます。

 for prime in primes:
   if '0' in str(prime):
     primes.remove(prime)
>>>>len(primes)
4026

...そして再び結果は次のようになります：

>>>>len(primes)
3892
....
3861 # again
....
3843 #and again

ここで明らかな何かが欠けているかもしれませんが、最初のif-testで「0」が含まれる素数を見つけて、それらをすべて削除する必要があるように見えましたか？

最後に、次のことも試しました。これは、str-integerの線路を無意味に前後にジャンプするため、ひどいようですが、機能する必要があるように見えました。

for num in primes:
  for d in str(num):
    if (int(d) % 2 == 0 or int(d) == 5):
      primes.remove(num)   # doesn't work: ValueError: list.remove(x): x not in list 
    else:
      pass

この質問で髪を引き裂くべきではないように感じますが、それは私を少し狂わせています、そしておそらく私が解決策をハックしようとしているところまで来たので、私の試みは少なくなっています明快。

これが私の質問です：

整数を反復処理してその中の他の整数を見つけ、それらが含まれている場合はその愚かな整数を破棄するための最良の方法は何ですか？

あなたの助け/読書をありがとう。

脚注：これは私がここで尋ねた最初の質問ですが、私はこのサイトのガイダンスから数か月間恩恵を受けています。この質問/解決策が存在する場合はお詫びしますが、私はそれを探しましたが、解決策をまとめる方法を見つけることができませんでした。ほとんどの検索結果は、「整数が偶数かどうかを判断する方法」として表示されます。

4

2 に答える 2

2

@root is correct that your assumption about how to optimise this is false, but I'd thought it'd be useful to point out why what you're doing isn't working on a Python level.

Your bool problem:

[num for num in primes if any(x for x in '024685' in str(num))] # failed: 'bool' object is not iterable

'024685' in str(num) is being evaluated first, so it equates to for x in True - which isn't possible. The above would be written as:

[num for num in primes if not any(ch in '024685' for ch in str(num)]

Which takes each character from str(num) and checks to see if it's one of '024685'.

Your list problem:

There's a rule of thumb here - don't modify something you're iterating over. If you were to try this with a dict you'd get an exception thrown - but for a list it's likely to get silently wrong, but occasionally will break.

When removing more than one value from a list, it's better to build a new list keeping only the required values, eg:

no_zero = [num for num in primes if '0' not in str(num)]

And if you wanted to modify the original primes:

primes[:] = no_zero

Your last example also fails because of .remove(), and putting the above together can be written as:

[num for num in primes if not any(num % i == 0 for i in (2, 5)]

Misc:

You may wish to consider storing the primes in a set - as you're not concerned about the order of the primes, and will be faster for membership testing.

于 2012-11-08T07:32:17.247 に答える
0

Thanks, Jon Clements. I was able to solve the problem today with the following script (note that I had to make sure the '024685' stripper did not strip out '2' and '5' because those were part of the answer, which threw me off for awhile...):

import math
import itertools

def prime_test(number):
  if all(number % x != 0 for x in range(2, int(math.sqrt(number)) + 1)):
    return True
  else:
return False

def find_primes(limit):
  primes = [2]
  for x in range(3, limit + 1, 2):
    if prime_test(x):
      primes.append(x)
    else:
      pass
  return primes

def circulate(number):
  circ_list = [number]
  x = 1
  while x < len(str(number)):
    number = str(number)[1:] + str(number)[0]
    circ_list.append(number)
    x += 1
  return circ_list

def main():
  primes = find_primes(1000000)
  no_evens = [x for x in primes if not any(ch in '024685' for ch in str(x) if len(str(x)) > 1)]

  circular_primes = [] 
  for prime in no_evens:
    if all(prime_test(x) for x in circulate(prime)):
      circular_primes.append(prime)
    else:
      pass

  return circular_primes, len(circular_primes)

if __name__ == '__main__':
  print(main())

Another thing I didn't realize is that I was merely supposed to rotate the number, not provide all possible permutations of it. These gotches probably throw people off when they're trying to solve the problem.

于 2012-11-11T01:34:09.597 に答える