計算方法 python

Question

1から43までの数字から6個の数字を選んでその和が52以下になる組み合わせが何通りあるかを計算したいのですがどうすれば良いですか？

Comments

[mather]

丸投げの質問では回答できません。まずはあなたが書いてみたPythonコードやどうやったら解決できるか考えた部分を断片的でもいいので教えてください。

[tiitoi]

DP の部分和問題で解けそうな気がします。

Answer 1

6 重の loop を書いて解いてみました。

x2.py

ans = 0
for a in range(1, 44):
    for b in range(a + 1, 44):
        for c in range(b + 1, 44):
            for d in range(c + 1, 44):
                for e in range(d + 1, 44):
                    for f in range(e + 1, 44):
                        if a + b + c + d + e + f <= 52:
                            ans += 1
print(ans)

a ＋ c ＋ 。。。＋ f は無駄に何回同じ計算をしているし、途中の小計が 52 以上になったらループは脱出してよいことを組み込んで見ました。

x3.py

ans = 0
for a in range(1, 44):
    s_a = a
    for b in range(a + 1, 44):
        s_b = s_a + b
        if s_b >= 52:
            break
        for c in range(b + 1, 44):
            s_c = s_b + c
            if s_c >= 52:
                break
            for d in range(c + 1, 44):
                s_d = s_c + d
                if s_d >= 52:
                    break
                for e in range(d + 1, 44):
                    s_e = s_d + e
                    if s_e >= 52:
                        break
                    for f in range(e + 1, 44):
                        s_f = s_e + f
                        if s_f <= 52:
                            ans += 1
print(ans)
```

時間計測も兼ねて次の shell script で実行してみました。
(x1.py は raccy さんの回答のコード)
x.sh
```sh
#!/bin/bash

echo "------- x1 ---------"
for i in {1..5} ; do
    time python3 x1.py
done

echo "------- x2 ---------"
for i in {1..5} ; do
    time python3 x2.py
done

echo "------- x3 ---------"
for i in {1..5} ; do
    time python3 x3.py
done
```

実行例
```
[katoy@katoy-MacBook-Pro-2 ttt]$ ./x.sh 
------- x1 ---------
9907

real	0m3.013s
user	0m2.144s
sys	0m0.101s
9907

real	0m2.298s
user	0m2.126s
sys	0m0.081s
9907

real	0m2.360s
user	0m2.174s
sys	0m0.086s
9907

real	0m2.376s
user	0m2.079s
sys	0m0.081s
9907

real	0m2.337s
user	0m2.182s
sys	0m0.075s
------- x2 ---------
9907

real	0m2.857s
user	0m2.661s
sys	0m0.082s
9907

real	0m2.769s
user	0m2.594s
sys	0m0.084s
9907

real	0m2.823s
user	0m2.632s
sys	0m0.087s
9907

real	0m3.834s
user	0m2.655s
sys	0m0.092s
9907

real	0m3.026s
user	0m2.823s
sys	0m0.087s
------- x3 ---------
9907

real	0m0.362s
user	0m0.165s
sys	0m0.068s
9907

real	0m0.306s
user	0m0.164s
sys	0m0.067s
9907

real	0m0.293s
user	0m0.154s
sys	0m0.067s
9907

real	0m0.294s
user	0m0.155s
sys	0m0.066s
9907

real	0m0.327s
user	0m0.166s
sys	0m0.078s
```

参考情報
- Pythonで順列・組み合わせを求める 
[https://qiita.com/BlueSilverCat/items/77f4e11d3930d7b8959b](https://qiita.com/BlueSilverCat/items/77f4e11d3930d7b8959b)

Answer 2

愚直なやり方ですが、Rubyだとこう書きます。

(1..43).to_a.combination(6).map(&:sum).select(&52.method(:>=)).size

これをPythonに書き直せば求めるコードになります。

と言いたいところですが、Pythonはmapやfilterは邪道という文化ですので、リスト内包表記を使います。

from itertools import combinations
len([x for x in combinations(range(1, 44), 6) if sum(x) <= 52])

なお、最適化を全くしていないので、これよりも速いアルゴリズムは存在します。

Comments

[yuudai]

自分ではどうにもなりませんでした。ありがとうございました。