上限がバラバラなリストでのnまでの総数の組み合わせ

Question

pythonで例えば
リストの各要素の上限が決まっており，その中にnを振り分ける方法はどのようにすればよいのでしょうか．

例：

max = [0,5,4,3,4,1]
n = 10

#リストの要素の総和がnになるような組み合わせ

[0,5,4,1,0,0]
[0,5,4,0,1,0]
[0,5,4,0,0,1]
…
[0,0,2,3,4,1]

Comments

[quickquip]

[0,0,2,3,4,1] の 2 はなんですか?

[mermer]

記述不足で申し訳ありません．
リスト内の総和がnになる組み合わせです．

[quickquip]

max = [0,5,4,3,4,1] が誤誘導ですか?
ここに2がないわけですが、この中から選びたいわけではなくとにかく10になればいいのですか?

[mermer]

リスト内の要素それぞれの上限がmax=[0,5,4,3,4,1]で
その中からリスト内の要素の総和がnになるようなリストを作り出したいわけです．
ですので[0,0,2,3,4,1]はリストの要素の総和が10かつリスト内の要素はmaxの値を超えてないという例でございます．

[quickquip]

了解しました。なるほど

Answer 1

データサイズにもよりますが再起呼び出しを使えばいいんではないでしょうか

def f(res, max_array, n, work_array):

    i = len(work_array)
    s = sum(work_array)

    # 組み合わせ配列の長さが最大値配列の長さに達したか？
    if (i == len(max_array)):
        # 組み合わせ配列の合計は目的の値か？
        if s == n:
            # 組み合わせ配列を結果用配列に追加
            res.append(work_array)
    else:
        # 残りの数値または対象要素の数値の小さいほうでループ
        for v in range(min(max_array[i], n-s)+1):
            w = work_array[:]
            # 選択した値を組み合わせ配列に追加する
            w.append(v)
            # 再起呼び出し
            f(res, max_array, n, w)


max_array = [0,5,4,3,4,1]
n = 10

res = []
work_array = []

f(res, max_array, n, work_array)


for _ in res:
    print(_)

Comments

[mermer]

quiquiさんの方法もよかったですが，こちらが私のマシンで実行速度が速かったためにベストアンサーにさせていただきました．

Answer 2

この程度のループなら、全組み合わせ(product)を生成してから、合計10のものだけにする(filter)という方針でもいいような気がします。
参考程度にどうぞ。

m = [0,5,4,3,4,1]  # max は変数名として使うべきではないので
n = 10

from itertools import product

range_argments = [x + 1 for x in m]  # => [1, 6, 5, 4, 5, 2]
answer = list(filter(lambda x: sum(x) == 10, product(*map(range, range_argments))))

print(answer)

[(0, 0, 2, 3, 4, 1), (0, 0, 3, 2, 4, 1), (0, 0, 3, 3, 3, 1), (0, 0, 3, 3, 4, 0), (0, 0, 4, 1, 4, 1), (0, 0, 4, 2, 3, 1),
 (0, 0, 4, 2, 4, 0), (0, 0, 4, 3, 2, 1), (0, 0, 4, 3, 3, 0), (0, 1, 1, 3, 4, 1), (0, 1, 2, 2, 4, 1), (0, 1, 2, 3, 3, 1),
 (0, 1, 2, 3, 4, 0), (0, 1, 3, 1, 4, 1), (0, 1, 3, 2, 3, 1), (0, 1, 3, 2, 4, 0), (0, 1, 3, 3, 2, 1), (0, 1, 3, 3, 3, 0),
 (0, 1, 4, 0, 4, 1), (0, 1, 4, 1, 3, 1), (0, 1, 4, 1, 4, 0), (0, 1, 4, 2, 2, 1), (0, 1, 4, 2, 3, 0), (0, 1, 4, 3, 1, 1),
 (0, 1, 4, 3, 2, 0), (0, 2, 0, 3, 4, 1), (0, 2, 1, 2, 4, 1), (0, 2, 1, 3, 3, 1), (0, 2, 1, 3, 4, 0), (0, 2, 2, 1, 4, 1),
 (0, 2, 2, 2, 3, 1), (0, 2, 2, 2, 4, 0), (0, 2, 2, 3, 2, 1), (0, 2, 2, 3, 3, 0), (0, 2, 3, 0, 4, 1), (0, 2, 3, 1, 3, 1),
 (0, 2, 3, 1, 4, 0), (0, 2, 3, 2, 2, 1), (0, 2, 3, 2, 3, 0), (0, 2, 3, 3, 1, 1), (0, 2, 3, 3, 2, 0), (0, 2, 4, 0, 3, 1),
 (0, 2, 4, 0, 4, 0), (0, 2, 4, 1, 2, 1), (0, 2, 4, 1, 3, 0), (0, 2, 4, 2, 1, 1), (0, 2, 4, 2, 2, 0), (0, 2, 4, 3, 0, 1),
 (0, 2, 4, 3, 1, 0), (0, 3, 0, 2, 4, 1), (0, 3, 0, 3, 3, 1), (0, 3, 0, 3, 4, 0), (0, 3, 1, 1, 4, 1), (0, 3, 1, 2, 3, 1),
 (0, 3, 1, 2, 4, 0), (0, 3, 1, 3, 2, 1), (0, 3, 1, 3, 3, 0), (0, 3, 2, 0, 4, 1), (0, 3, 2, 1, 3, 1), (0, 3, 2, 1, 4, 0),
 (0, 3, 2, 2, 2, 1), (0, 3, 2, 2, 3, 0), (0, 3, 2, 3, 1, 1), (0, 3, 2, 3, 2, 0), (0, 3, 3, 0, 3, 1), (0, 3, 3, 0, 4, 0),
 (0, 3, 3, 1, 2, 1), (0, 3, 3, 1, 3, 0), (0, 3, 3, 2, 1, 1), (0, 3, 3, 2, 2, 0), (0, 3, 3, 3, 0, 1), (0, 3, 3, 3, 1, 0),
 (0, 3, 4, 0, 2, 1), (0, 3, 4, 0, 3, 0), (0, 3, 4, 1, 1, 1), (0, 3, 4, 1, 2, 0), (0, 3, 4, 2, 0, 1), (0, 3, 4, 2, 1, 0),
 (0, 3, 4, 3, 0, 0), (0, 4, 0, 1, 4, 1), (0, 4, 0, 2, 3, 1), (0, 4, 0, 2, 4, 0), (0, 4, 0, 3, 2, 1), (0, 4, 0, 3, 3, 0),
 (0, 4, 1, 0, 4, 1), (0, 4, 1, 1, 3, 1), (0, 4, 1, 1, 4, 0), (0, 4, 1, 2, 2, 1), (0, 4, 1, 2, 3, 0), (0, 4, 1, 3, 1, 1),
 (0, 4, 1, 3, 2, 0), (0, 4, 2, 0, 3, 1), (0, 4, 2, 0, 4, 0), (0, 4, 2, 1, 2, 1), (0, 4, 2, 1, 3, 0), (0, 4, 2, 2, 1, 1),
 (0, 4, 2, 2, 2, 0), (0, 4, 2, 3, 0, 1), (0, 4, 2, 3, 1, 0), (0, 4, 3, 0, 2, 1), (0, 4, 3, 0, 3, 0), (0, 4, 3, 1, 1, 1),
 (0, 4, 3, 1, 2, 0), (0, 4, 3, 2, 0, 1), (0, 4, 3, 2, 1, 0), (0, 4, 3, 3, 0, 0), (0, 4, 4, 0, 1, 1), (0, 4, 4, 0, 2, 0),
 (0, 4, 4, 1, 0, 1), (0, 4, 4, 1, 1, 0), (0, 4, 4, 2, 0, 0), (0, 5, 0, 0, 4, 1), (0, 5, 0, 1, 3, 1), (0, 5, 0, 1, 4, 0),
 (0, 5, 0, 2, 2, 1), (0, 5, 0, 2, 3, 0), (0, 5, 0, 3, 1, 1), (0, 5, 0, 3, 2, 0), (0, 5, 1, 0, 3, 1), (0, 5, 1, 0, 4, 0),
 (0, 5, 1, 1, 2, 1), (0, 5, 1, 1, 3, 0), (0, 5, 1, 2, 1, 1), (0, 5, 1, 2, 2, 0), (0, 5, 1, 3, 0, 1), (0, 5, 1, 3, 1, 0),
 (0, 5, 2, 0, 2, 1), (0, 5, 2, 0, 3, 0), (0, 5, 2, 1, 1, 1), (0, 5, 2, 1, 2, 0), (0, 5, 2, 2, 0, 1), (0, 5, 2, 2, 1, 0),
 (0, 5, 2, 3, 0, 0), (0, 5, 3, 0, 1, 1), (0, 5, 3, 0, 2, 0), (0, 5, 3, 1, 0, 1), (0, 5, 3, 1, 1, 0), (0, 5, 3, 2, 0, 0),
 (0, 5, 4, 0, 0, 1), (0, 5, 4, 0, 1, 0), (0, 5, 4, 1, 0, 0)]

Comments

[退会済みユーザー]

answer = list... の行、閉じカッコが一つ不足しています。

[quickquip]

ありがとうございます。助かります。

Answer 3

リストの先頭要素から順に1つずつ計算する方式で作ってみました。
n=10くらいであれば、十分高速に動作すると思います。

def solve(n, limits):
    stack = [(n, sum(limits), [])]
    ans = []
    while stack:
        rem, t, picks = stack.pop()  # 合計でnにするために必要な残り、 実現可能な最大値、 これまで選択した数値のリスト
        if len(picks) == len(limits) - 1:
            if 0 <= rem <= limits[-1]:
                ans.append(picks + [rem])
        else:
            for i in range(max(rem-t, 0), min(rem+1, limits[len(picks)]+1)):
                stack.append((rem-i, t-limits[len(picks)], picks + [i]))
    return ans


limits = [0, 5, 4, 3, 4, 1]
n = 10

ans = solve(n, limits)
print(*ans, sep='\n')
print(len(ans))  # 141通り

Answer 4

1. 配列a[]の要素数をsとして
2. N > 0 である間:
3.     i=0～s-1の乱数
3.     a[i] が上限に満たなければ:
    　     a[i] += 1
           N -= 1

...と、こんなんでいかがでしょ。