やること

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

[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

import math
import tqdm

permutation

2個選ぶ用の関数
https://docs.python.org/3/library/itertools.html#itertools.permutations を改変。

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で高速化したかったのでリストが返ってきてほしかったため。

+-*/の並べ替え

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を並べ替えて結合

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 が出る可能性があるため。

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

実行部

whileでretにできたものを、noretにまだできていないやつを追加して実行。
最終的にやっていることは、

[1,2,3] ->
["(1+2)",3],[3,"(1+2)"] ... ->
"((1+2)+3)","((1+2)*3)" ... "(3+(1+2))","(3*(1+2))", ...

みたいな感じ。

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

実行

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秒ほど。

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でもやってみたが、１秒ほどしか変わらなかった。