配列要素の合計値がターゲット値になる様な組み合わせを全て求める

Python two sub sets all sum variants [on hold] – StackOverflow

最初,何の事か分からなかったけど,多分標題の通りだろう.とすると,

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

と同様に,numpyでブロードキャストを利用すれば簡単に解ける.

この質問は重複なし(リピート無し)なので,もっとシンプル.
(ターゲット毎のグリッドを考えなくて良いから)

import numpy as np

a1 = [100, 200, 300, 400, 500]
a2 = [200, 300, 500, 30, 70]

N = len(a1) - 1
elm = []
for i, e in enumerate(a1):
    temp = [1] * (N - i)
    elm.append(np.array([0, e]).reshape(-1, *temp))

res = 0
for x in elm:
    res = res + x

for t in a2:
    print(np.argwhere(res == t))

[[0 1 0 0 0]]
[[0 0 1 0 0]
[1 1 0 0 0]]
[[0 0 0 0 1]
[0 1 1 0 0]
[1 0 0 1 0]]
[]
[]

整形して表示すれば,

for t in a2:
    print('------'*30)
    print(f'target value: {t}')
    a = np.argwhere(res == t)
    if len(a) == 0:
        print('no matching')
    else:
        for x in a:
            if hasattr(x[0], '__iter__'):
                for e in x:
                    print(f'100: {e[0]}, 200: {e[1]}, 300: {e[2]}, 400: {e[3]}, 500: {e[4]}')
            else:
                print(f'100: {x[0]}, 200: {x[1]}, 300: {x[2]}, 400: {x[3]}, 500: {x[4]}')
    print('\n')

target value: 200
100: 0, 200: 1, 300: 0, 400: 0, 500: 0


target value: 300
100: 0, 200: 0, 300: 1, 400: 0, 500: 0
100: 1, 200: 1, 300: 0, 400: 0, 500: 0


target value: 500
100: 0, 200: 0, 300: 0, 400: 0, 500: 1
100: 0, 200: 1, 300: 1, 400: 0, 500: 0
100: 1, 200: 0, 300: 0, 400: 1, 500: 0


target value: 30
no matching


target value: 70
no matching
 
 
 

重複ありの場合,

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

と考え方は全く同じで,ここではロジックだけ示しておくと,

重複ありの組み合わせで合計値が500となる様な場合は,

t = 500

N = len(a1) - 1
elm = []
for i, step in enumerate(a1):
    temp = [1] * (N - i)
    elm.append(np.arange(0, t+1, step).reshape(-1, *temp))

res = 0
for x in elm:
    res = res + x

for x in np.argwhere(res == t):
    print(f'100: {x[0]}, 200: {x[1]}, 300: {x[2]}, 400: {x[3]}, 500: {x[4]}')

100: 0, 200: 0, 300: 0, 400: 0, 500: 1
100: 0, 200: 1, 300: 1, 400: 0, 500: 0
100: 1, 200: 0, 300: 0, 400: 1, 500: 0
100: 1, 200: 2, 300: 0, 400: 0, 500: 0
100: 2, 200: 0, 300: 1, 400: 0, 500: 0
100: 3, 200: 1, 300: 0, 400: 0, 500: 0
100: 5, 200: 0, 300: 0, 400: 0, 500: 0

ターゲットアレイを処理するには,全体をループで括れば良い.

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

配列要素の合計値がターゲット値になる様な組み合わせを全て求める への4件のフィードバック

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

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

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

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

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中