Pythonでテンパズルのn個の数字で好きな数字を作りたい

# やること
+ n個の数字から2つを選んで +-x÷をすべて並べ替えて出力
`[1,2] -> ['(1+2)', '(1-2)', '(1*2)', '(1/2)']` みたいに
+ 繰り返す
```py
[1,2,3] ->
[['(1+2)', 3], ['(1-2)', 3], ['(1*2)', 3], ['(1/2)', 3]] -> 
['((1+2)+3)', '((1+2)-3)', '((1+2)*3)', '((1+2)/3)' ... ]
```
みたいに

# コード
## import
```py
import math
from tqdm import tqdm
```
## permutation
2個選ぶ用の関数
https://docs.python.org/3/library/itertools.html#itertools.permutations を改変。
```py
def permutations(iterable, r=None):
    pool = list(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    x=[]
    x.append(list(pool[i] for i in indices[:r]))
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                x.append(list(pool[i] for i in indices[:r]))
                break
        else:
            return x
```
`itertools.permutations()`でもよかったが、Cythonで高速化したかったのでリストが返ってきてほしかったため。

## +-*/の並べ替え
```py
def insert(nums):
    if not isinstance(nums,list):
        return nums
    ret=[]
    for i in ["+","-","*","/"]:
        num=nums.copy()
        num.insert(1,i)
        ret.append("("+"".join([str(i) for i in num])+")")
    return ret


print(insert([1,2]))
#['(1+2)', '(1-2)', '(1*2)', '(1/2)']
```

## listを並べ替えて結合
```py
def combine(x,y):
    x=x if isinstance(x,list) else [x]
    y=y if isinstance(y,list) else [y]
    x=[i if isinstance(i,list) else [i] for i in x]
    y=[i if isinstance(i,list) else [i] for i in y]
    ret=[]
    for i in x:
        for j in y:
            ret.append(i+j)
    return ret

def combine_all(x):
    if len(x)==1:
        return x[0]
    if len(x)==2:
        return combine(x[0],x[1])
    else:
        y=combine(x[0],x[1])
        for i in x[2:]:
            y=combine(y,i)
        return y

print(combine_all([[1,2],[3,4],5]))
#[[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]
```

## 例外処理
実行時に`ZeroDivisionError` が出る可能性があるため。
```py
def execute(i,t):
    try:
        if eval(i)==t:
            return i
        else:
            return False
    except:
        return False
```

## 実行部
`while`で`ret`にできたものを、`noret`にまだできていないやつを追加して実行。
最終的にやっていることは、
```py
[1,2,3] ->
["(1+2)",3],[3,"(1+2)"] ... ->
"((1+2)+3)","((1+2)*3)" ... "(3+(1+2))","(3*(1+2))", ...
```
みたいな感じ。

```py
def get(nums,a):
    nums=[nums]
    ret=[]
    while True:
        noret=[]
        for num in nums:
            perms=permutations(num,2)
            for perm in perms:
                inserted=insert(perm)
                if len(num)==2:
                    ret+=inserted
                    continue
                x=num.copy()
                for i in perm:
                    x.remove(i)
                x.append(inserted)
                noret+=combine_all(x)
        if noret:
            nums=noret
        else:
            val=[]
            for i in tqdm(set(ret)):
                if x:=execute(i,a):
                    val.append(i)
            return val
```
## 実行
```py
print(get([1,1,9,9],10))
#['(9*((1/9)+1))', '((1+(1/9))*9)', '(((1/9)+1)*9)', '(9*(1+(1/9)))']
```

5個の数字の場合、平均10秒ほど。
```pyx
import math
from tqdm import tqdm

cdef list permutations(list iterable,int r):
    cdef:
        list pool=iterable
        int n = len(pool)
    if r > n:
        return
    cdef:
        list indices = list(range(n))
        list cycles = list(range(n, n-r, -1))
        list x=[]
        int i,j,k,l
    x.append(list(pool[k] for k in indices[:r]))
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                x.append(list(pool[l] for l in indices[:r]))
                break
        else:
            return x

cdef insert(nums):
    if not isinstance(nums,list):
        return nums
    cdef:
        list ret=[]
        list f=["+","-","*","/"]
        list j,num
        str x=""
        str i
    for i in f:
        num=nums.copy()
        num.insert(1,i)
        ret.append("("+"".join([str(k) for k in num])+")")
    return ret

cdef combine(d,f):
    cdef:
        list a=d if isinstance(d,list) else [d]
        list b=f if isinstance(f,list) else [f]
        list x=[p if isinstance(p,list) else [p] for p in a]
        list y=[q if isinstance(q,list) else [q] for q in b]
        list ret=[]
        list i,j
    for i in x:
        for j in y:
            ret.append(i+j)
    return ret

cdef list combine_all(list x):
    cdef list y
    if len(x)==1:
        return x[0]
    if len(x)==2:
        return combine(x[0],x[1])
    else:
        y=combine(x[0],x[1])
        for i in x[2:]:
            y=combine(y,i)
        return y

cdef execute(str i,t):
    try:
        if eval(i)==t:
            return i
        else:
            return False
    except:
        return False

def get(list numbers,int a):
    cdef:
        list nums=[numbers]
        list ret=[]
        list noret=[]
        list val=[]
        list perms,num,x,inserted
        str k
    while True:
        noret=[]
        for num in nums:
            perms=permutations(num,2)
            for perm in perms:
                inserted=insert(perm)
                if len(num)==2:
                    ret+=inserted
                    continue
                x=num.copy()
                for i in perm:
                    x.remove(i)
                x.append(inserted)
                noret+=combine_all(x)
        if noret:
            nums=noret
        else:
            val=[]
            for k in tqdm(set(ret)):
                if execute(k,a):
                    val.append(k)
            return val
```
Cythonでもやってみたが、１秒ほどしか変わらなかった。

# 後日短くした
```py
import os
os.environ["OPENBLAS_NUM_THREADS"] = "16"
os.environ["MKL_NUM_THREADS"] = "16"
os.environ["VECLIB_NUM_THREADS"] = "16"
from tqdm import tqdm
import numpy as np
from multiprocessing import Pool
import sys
import time
import threading
import itertools

def products(x):
    for i in x[-1]:
        yield x[:-1]+[i]
        
def insert(nums):
    s1,s2=nums[0],nums[1]
    n1,n2=convert(s1),convert(s2)
    return [f"{s1}+{s2}", f"{s1}-{s2}", f"{s2}-{s1}", f"{n1}*{n2}", f"{n1}/{n2}", f"{n2}/{n1}"]

def numpy_combinations(x):
    idx = np.stack(np.triu_indices(len(x), k=1), axis=-1)
    return x[idx]

def convert(i):
    return f"({i})" if ("+" in i or "-" in i) else i

def execute(i,targetn):
    try:
        if eval(i)==targetn:
            return i
        else:
            return False
    except ZeroDivisionError:
        return False

def get1(x):
    if len(x)>2:
        for comb in numpy_combinations(np.array(x)):
            y=sorted(x,key=(list(comb)+x).index)[2:]
            y.append(insert(comb))
            for i in products(y):
                yield from get1(i)
    else:
        for i in insert(x):
            yield i

done=False
    
def animate():
    for c in itertools.cycle(['|', '/', '-', '\\']):
        if done:
            break
        sys.stdout.write('\rGenerating all expressions  ' + c)
        sys.stdout.flush()
        time.sleep(0.1)
    sys.stdout.write('\rDone!')
    
def task():
    global done
    p2=Pool(16)
    x=input("input numbers with space like '1 2 3 4' > ").split(" ")
    targetn=int(input("input target number. > "))
    t = threading.Thread(target=animate)
    t.start()
    s=time.time()
    done=True
    print(list(filter(lambda i:i,p2.starmap(execute,tqdm(list(map(lambda i:(i,targetn),set(get1(x)))))))))
    e=time.time()
    print(f"Took {e-s}s")

if __name__=="__main__":
    task()
```

treadingにより並列処理を導入。