5

いくつかの最大値までの、いくつかの整数因子のすべての可能な積を列挙したい:

  • P((2, 3, 11), 10)戻り(2, 3, 4, 6, 8, 9)ます。
  • P((5, 7, 13), 30)戻り(5, 7, 13, 25)ます。

これは、枝が最大に達すると成長を停止するツリー トラバーサルのように見えますが、枝の数の境界が何であるかはわかりません。この問題に推奨されるアルゴリズムまたはイディオムは何ですか? 私がこれまでに見た中で最も近いのは です。これはitertools.product()、出力セットごとに固定数の用語を設定しているようです (例: 2)。

コンテキストとして、n と互いに素な数値を調べようとしています。この場合、n 自体が上限であり、因子のリストは n のものです。上記の質問を少し一般化しようとしました。

4

3 に答える 3

3

入力リストのすべての要素で 1 を乗算し、すべての結果を入力リストの要素で乗算するなど、制限に達するまで、この方法が気に入っています。

def signature_seq(signature, limit):
  products = set((1,))
  for factor in signature:
    new_products = set()
    for prod in products:
      x = factor * prod
      while x <= limit:
        new_products.add(x)
        x *= factor
    products.update(new_products)

  products.remove(1)
  return products

これはあなたが望むことをするはずです：

>>> print(sorted(signature_seq((2, 3, 11), 10)))
[2, 3, 4, 6, 8, 9]
>>> print(sorted(signature_seq((5, 7, 13), 30)))
[5, 7, 13, 25]

ちなみに、2 から始まる連続した素数のリストが与えられた場合、これは滑らかな数生成器です。

于 2013-07-25T01:13:50.013 に答える