総組み合わせのアルゴリズム

Question

前提・実現したいこと

pythonで要素を5つもつリストに10をそれぞれ振り分けた総組み合わせを出すアルゴリズムが書けません．
何かお知恵をお貸しいただけないでしょうか？
お恥ずかしながら，私は全くの初心者で今回の問題に最初の一歩もコードが書けておりません．

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

a = [0,0,0,0,0]

ほしい結果：

[10,0,0,0,0]
[9,1,0,0,0]
[9,0,1,0,0]
・
・
・
[8,2,0,0,0]
[8,1,1,0,0]
[8,1,0,1,0]
・
・
・
[0,0,0,1,9]
[0,0,0,0,10]

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

■■■■■■■■■■
の、■の間と、両端に4枚の仕切り板をどこかに入れる問題です(1箇所に何枚入れてもいい)。

||||■■■■■■■■■■
なら
0, 0, 0, 0, 10

■|■■■|■■|■■|■■
なら
1, 3, 2, 2, 2

に対応します。

---

「仕切り板の位置」をitertools.combinations_with_replacementを使って列挙します。

||||■■■■■■■■■■
なら仕切り板の位置のタプルは
(0, 0, 0, 0)

■|■■■|■■|■■|■■
なら仕切り板ののタプル位置
(1, 4, 6, 8)
です。

from itertools import combinations_with_replacement

result = []
for x in combinations_with_replacement(range(11), 4):
    st = 0
    seq = []
    for i in x:
        seq.append(i - st)
        st = i
    seq.append(10 - i)
    result.append(seq)

となります。

列挙の順番は順序は逆ですが。

---

result = []
for x in combinations_with_replacement(range(11), 4):
    result.append([ed - st for st, ed in zip((0,) + x, x + (10,))])

でも。

Comments

[mermer]

問題を数学的に捉えるいい訓練になりました．
良い回答をありがとうございます．

Answer 2

問題はこういうことですか？

• a + b + c + d + e = 10 となる、a, b, c, d, e （それぞれ >= 0 の整数）の組み合わせを全て出力せよ
• a, b, c, d, e の値は重複しても構わない

題意から、a,b,c,d,e は、0 ～ 10 の範囲の値しか取り得ません。

ですので、強引な力業としては、

a を 0～10 までループ
  b を 0～10までループ
    c を 0～10までループ
      d を 0 ～10 までループ
        e = 10-(a+b+c+d)
        e>=0 かつ e <= 10 なら、a,b,c,d,e を出力

でもできることはできますね。

Comments

[退会済みユーザー]

総当りして合致したものを拾う。。。コンピュータの得意なやつですねｗ
この問題だと力技って言っちゃうのも分かりますが、ごく普通のアプローチでもあると思います。

[tacsheaven]

中のループの終端は10でなくてもよい、とか、いくつか小技はあるとは思いますが、まあ愚直もよいかと（ｗ

[mermer]

総当たりで合致したものを拾うのは考えていなかったです．
最初からスマートに書こうとするものじゃないですね．
勉強になりました．

Answer 3

リストの生成・追加

生成されるリストの順番を考慮しなくてよいのであれば、単純に5重ループを回して全探索すればよいと思います。

lst = []  # 最初に空っぽのリストを作成しておきます

for a in range(0, 11):  # aは0~10までループします
    for b in range(0, 11):  # bは0~10までループします
        for c in range(0, 11):  # cは0~10までループします
            for d in range(0, 11):  # dは0~10までループします
                for e in range(0, 11):  # eは0~10までループします
                    if a+b+c+d+e == 10:  # 和が10のとき、lstの末尾にリストを追加します
                        lst.append([a, b, c, d, e])

# 確認のため、lstの中身を一つずつ出力します
for l in lst:
    print(l)

[0, 0, 0, 0, 10]
[0, 0, 0, 1, 9]
[0, 0, 0, 2, 8]
[0, 0, 0, 3, 7]
[0, 0, 0, 4, 6]
[0, 0, 0, 5, 5]
[0, 0, 0, 6, 4]
...

また、eの値は必ずe = 10 - (a+b+c+d)なので、簡単にループをひとつ減らすことができます（計算量を減らして高速化することができます）。

lst = []  # 最初に空っぽのリストを作成しておきます

for a in range(0, 11):
    for b in range(0, 11):
        for c in range(0, 11):
            for d in range(0, 11):
                e = 10 - (a+b+c+d)
                if e >= 0:  # eが0以上なら、リストに追加する
                    lst.append([a, b, c, d, e])


# 確認のため、lstの中身を一つずつ出力します
for l in lst:
    print(l)

#リストのソート
Pythonではリストをソートすることができます。

# 昇順にソート
lst.sort()

[0, 0, 0, 0, 10]
[0, 0, 0, 1, 9]
[0, 0, 0, 2, 8]
[0, 0, 0, 3, 7]
[0, 0, 0, 4, 6]
[0, 0, 0, 5, 5]
...

質問の並び順の場合、降順にソートすればよいかもしれません。

# 降順にソート
lst.sort(reverse=True)

[10, 0, 0, 0, 0]
[9, 1, 0, 0, 0]
[9, 0, 1, 0, 0]
[9, 0, 0, 1, 0]
[9, 0, 0, 0, 1]
[8, 2, 0, 0, 0]
[8, 1, 1, 0, 0]
[8, 1, 0, 1, 0]
...