すべての部分集合の数字の和を求める

以下のような問題を考えます。

すべての部分集合の数字の和を求める問題

問題： トランプの52枚の集合のすべての部分集合を作り各々の数字の和を求めたとき１の位の数で一番多いのはどれ？

1桁の数字の数をカウントする配列countを定義します。

import numpy as np
count = np.array([0]*10)
#[0 0 0 0 0 0 0 0 0 0]

部分集合はまず空集合${}$から初めて、それまでの部分集合のすべてに、新たな要素加えたものを追加行くと考えられます。$1,2,..$と加えて行くと考えると以下のようになります。

\{ \{ \} \} \rightarrow \{ \{ \} \{ 1\}  \}  
 \rightarrow \{ \{ \} \{ 1\} \{ 2 \} \{ 1, 2\} \}  

これを数字の和のカウントを考えると、１を加えるということは右に１つ動くということなので、１つ右に回転して前のものと足せば良いことになります。

[1 0 0 0 0 0 0 0 0 0]    # 空集合（和は0が一つ）
---------------------------------
[0 1 0 0 0 0 0 0 0 0]    # 1を加える = 一つ右に回転
[1 1 0 0 0 0 0 0 0 0]    # 前のものと足す
---------------------------------
[0 0 1 1 0 0 0 0 0 0]    # 2を加える = ２つ右に回転
[1 1 1 1 0 0 0 0 0 0]    # 前のものと足す

これは$0,1,2,3$が一つずつあるということなので結果と一致しています。

従って元の問題はこの「countを次に加える数だけ回転して、足し合わせる」を繰り返せばよいので、以下のようなコードになります。結果は見づらいですが2と7が最大になります。

import numpy as np
import sympy
cards =[n for n in range(1,14)]*4

count = np.array([0]*10)
count[0] = 1

for n in cards:
  count += np.roll(count,n) # rotate and add 

print(count)
#[450359962737152 450359962736768 450359962737408 450359962736768
 450359962737152 450359962737152 450359962736768 450359962737408
 450359962736768 450359962737152]

このアルゴリズムはEuler Project: Problem 249, 250を解くのに役に立ちます。

（開発環境：Google Colab）