Python初心者(中学生)の組み合わせ生成が斜め上だった件（再帰処理で組み合わせ生成）

# 数学パズル

Python勉強中のK君[数学パズル](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E8%84%B3%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%E6%95%B0%E5%AD%A6%E3%83%91%E3%82%BA%E3%83%AB-%E3%82%B7%E3%83%B3%E3%83%97%E3%83%AB%E3%81%A7%E9%AB%98%E9%80%9F%E3%81%AA%E3%82%B3%E3%83%BC%E3%83%89%E3%81%8C%E6%9B%B8%E3%81%91%E3%82%8B%E3%82%88%E3%81%86%E3%81%AB%E3%81%AA%E3%82%8B70%E5%95%8F-%E5%A2%97%E4%BA%95-%E6%95%8F%E5%85%8B/dp/479814245X/ref=asc_df_479814245X/?tag=jpgo-22&linkCode=df0&hvadid=295723231663&hvpos=1o1&hvnetw=g&hvrand=6299120856193524254&hvpone=&hvptwo=&hvqmt=&hvdev=c&hvdvcmdl=&hvlocint=&hvlocphy=1009242&hvtargid=pla-526233948639&psc=1&th=1&psc=1)
これの第二回目。

四桁の数字の間に四則演算を入れて式にして、演算した結果がもとの数字の逆順と一致する条件を探す問題。四則演算は最低１か所入れる。
答えを書いてしまうと、
5931 5*9*31 = 1395
これが答えです。総当たりで調べて条件に一致するものを求めます。

ざっくり、こんなプログラムでしょうね。

```python
op_table = ["","+","-","*","/"]
for number in range(1000,10000):
    for op1 in op_table:
        for op2 in op_table:
            for op3 in op_table:
                if check(number,op1, op2, op3):
                    print(number,op1, op2, op3)
```

# Python初心者作品

```python
def Quinary(n):
    if (int(n/5)):
        return Quinary(int(n/5)) + str(n%5)
    return str(n%5)

def eval_change(a):
    b = list_change(a)
    try:
        return int(eval(b))
    except ZeroDivisionError:
        return -1
    except SyntaxError:
        return -1
   
def list_change(a):
    b = ""
    for l in a:
        b += l
    return b

table = ["","+","-","*","/"]
for i in range(1000,10000):
    for j in range(1,125):
        a = (Quinary(j).zfill(3))
        b = list(str(i))
        for k in range(3):
            b.insert(k*2+1,table[int(a[k])])
        if str(eval_change(b)) == str(i)[::-1]:
            print(i,list_change(b),"=",int(str(i)[::-1]))
```

おいおい。K君は、２重ループで解くという道を選びました。
かなり険しい道を選んだ感がありますが、よく解けたね。
Quinaryはネットで調べてもってきたそうです。演算子は５種類だから、５進数を使おうという発想。
この発想はなかった。

このプログラムの肝は、再帰使うことで、組み合わせを生成している所。
わざわざ５進数を持ち出してくるのはいただけないが、多重ループ使わなくても総当たりを生成できるんじゃない？
それにこの方法は、パラメータを変えれば何桁でも実現できる可能性を秘めている。

という訳で、平凡な４重ループ以外の方法でこの問題を解いてみます。

## SyntaxErrorを防止

大改造する前に、気になる部分を修正

pythonでは、01 001など0数字の前に0があるとSyntaxErrorとなります。このため、eval("1+001")は、SyntaxErrorとなります。
K君は、このような場合は計算しない作戦をとりました。正解はこのパターンではなかったので、答えが求まりました。
正確には、総当たりになってないので、エラーにならないように（計算式を作る時に、不要な0を追加しないように）してました。
計算式を作った後で、正規表現で0削除する手もありそうですね。

# 料理開始

演算子の組み合わせ生成するジェネレータを再帰で作成。


```python:gen_sequence

a0=[["a","b"],["A","B","C"]]

def gen_sequence(a):
    for i in a[0]:
        if(len(a)>1):
            for j in gen_sequence(a[1:]):
                yield([i]+j)
        else:
            yield([i])

for x in gen_sequence(a0):
    print(x)
```

```console:実行結果
['a', 'A']
['a', 'B']
['a', 'C']
['b', 'A']
['b', 'B']
['b', 'C']
```

演算子の組み合わせをgen_sequenceで生成して、総当たりで条件に合うか調べます。
K君の計算式の文字列を生成する処理は、かなりトリッキーだったので、zipを使った処理に書き直して、関数化しました。

```python
from itertools import zip_longest

op_list=[["","+","-","*","/"]]*3

def gen_sequence(a):
    for i in a[0]:
        if(len(a)>1):
            for j in gen_sequence(a[1:]):
                yield([i]+j)
        else:
            yield([i])

def build_formula(number_str, ops):
    formula = ""
    for num, op in zip_longest(number_str , ops, fillvalue=""):
        if len(formula)>1 and not formula[-2].isdigit() and formula[-1]=="0":
            # 演算子直後の0は削除する
            formula = formula[:-1]
        formula += num + op
    return formula

def eval_string(string):
    try:
        return eval(string)
    except ZeroDivisionError:
        return -1
           
for i in range(1000,10000):
    number_str = str(i)
    number_str_rev = number_str[::-1]
    for op in gen_sequence(op_list):
        if op ==[""]*3:
            continue
        formula = build_formula(number_str, op)
        if str(eval_string(formula)) == number_str_rev:
            print(i , formula , "=" , number_str_rev)
```

ループを使わないで総当たりの組み合わせを生成にこだわってみました。
2020/01/01 zip_longest()に変更

gen_sequence関数を作成しましたが、itertools.product(*op_list)がこれと等価でした。
この関数を作る事が目的なので、今回は作りましたが、この機能が必要な時は、itertools.productを使えばいいと思います。