How can I list all of the ways to sum a list of numbers to N, with repeats, in python?

How can I list all of the ways to sum a list of numbers to N, with repeats, in python? – StackOverflow

テクニカルに解く方法は分からないけど,(素因数分解して解けば良いだろうか)
クルードに解くなら,色々な場面で活用しているあの手がある.

import numpy as np

a = np.arange(0, 9, 2)[:, np.newaxis, np.newaxis, np.newaxis, np.newaxis]
b = np.arange(0, 9, 4)[:, np.newaxis, np.newaxis, np.newaxis]
c = np.arange(0, 9, 5)[:, np.newaxis, np.newaxis]
d = np.arange(0, 9, 6)[:, np.newaxis]
e = np.arange(0, 9, 7)

np.argwhere(a+b+c+d+e == 8)

array([[0, 2, 0, 0, 0],
[1, 0, 0, 1, 0],
[2, 1, 0, 0, 0],
[4, 0, 0, 0, 0]], dtype=int64)

インデックスマトリックスはそのまま値に対応しているので,
上のアレイを値に置き換えれば,

4 x 2
2 x 1 + 6 x 1
2 x 2 + 4 x 1
2 x 4

という形で,きちんと求まっている事が分かる.

多分,ブルートフォースなメソッドとしては最も実効性が高いんじゃないだろうか.
 
 
 

ピュアPythonにやろうと思うと,バイナリツリーを考えるのが良いんじゃないだろうか.

binary_tree

広告
カテゴリー: 未分類 パーマリンク

How can I list all of the ways to sum a list of numbers to N, with repeats, in python? への6件のフィードバック

  1. ピンバック: 配列要素の合計値がターゲット値になる様な組み合わせを全て求める | 粉末@それは風のように (日記)

  2. ピンバック: 整数配列からa + b + c = 0を満たす様な組み合わせを求める | 粉末@それは風のように (日記)

  3. ピンバック: 2つのnumpy.ndarrayのマッチング | 粉末@それは風のように (日記)

  4. ピンバック: 部分和問題 | 粉末@それは風のように (日記)

  5. ピンバック: 制約最適化問題の実現可能な領域を視覚化したい | 粉末@それは風のように (日記)

  6. ピンバック: 決定木を可視化する | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中