Python 算法/函数 : return all of the operational combinations of the digits of an input number which equal a target number

Question

我的任务是生成一个函数 f，在给定输入数字和目标数字的情况下，该函数将返回构成目标数字的输入的所有操作组合(+、-、/、* 和连接数字)。例如，如果输入和目标数字是 115 和 16，则程序应返回 11+5=16。输入 f(123,6) 应该产生 1+2+3=6 和 1*2*3=6。 f(12301,6) 应该返回 1+2+3+0*1=6, 1+2+3-0*1=6, 1 *2*3+0*1=6, 1*2*3-0*1=6, 1+2*3+0-1=6 code>，和 1+2*3-0-1=6。

这是我到目前为止的尝试。我试图递归地解决这个问题，但在开发可靠的算法时遇到了麻烦。递归算法是解决此问题的正确方法吗？

"""
creates a list of the integers associated with input number and returns all the
ways that list of numbers can be ordered with +-*/ operators to form target_num
base specifies which number system is being used (base 10 is default)
"""
TASKS = ['add','mul','sub','div','con']
def consec_op_types(num_in, target_num, base = 10):

    # get digits
    digits = []
    while num_in >1:
        next_smallest_number = num_in % base
        num_in = num_in / 10
        digits.append(next_smallest_number)
    digits.append(num_in)
    digits.reverse()

    '''
    A recursive scheme is used to find the combinations.
    Each function call in turn calls +-/* operators as well as just using this number with the one next to it
    '''

    # accepts list of operators used, references digits from above
    def show_results(vals):
        # print [item for sublist in zip(vals,digits) for item in sublist], ' = ', target_num
        print ''.join([str(v) for v in vals]), '=', target_num


    def find_number(num_list,total= 0,task= 0, result = []):
        print 'total:',total
        if num_list == [] :
        #    if total != 0: print total, result
            if total ==target_num: show_results(result)
            return

        if total==0:
           if task == TASKS[3] or task == TASKS[1]: total = 1

        #print "result = result+['+']",result+['+']
        #print 'total:',total
        if task in TASKS:
            current_num = num_list[0]
            num_list = num_list[1:]
            result.append(current_num)
        if task == TASKS[0]:
            return find_number(num_list, total + current_num,  0,  result+['+'])

        if task == TASKS[1]:
            return find_number(num_list, total * current_num,  task = 0,result = result+['*'])

        if task == TASKS[2]:
            return find_number(num_list, total + current_num, task = 0, result = result+['-'])

        if task == TASKS[3]:
            if current_num != 0: return find_number(num_list, total / current_num, task = 0, result = result+['/'])

        if task == TASKS[4] and len(num_list)>1:
            print 'ok.... num_list is ',num_list,' and current num is ',current_num
            print '--->',[10*current_num + num_list[0]]+num_list[1:]

            return find_number( [10*current_num + num_list[0]] + num_list[1:], 
                                 total,  0, result[:-1])

        #find_number(num_list, total, TASKS[0], result)
        for tk in TASKS:
            find_number(num_list, total, tk, result)
    find_number(digits)

# Object oriented idea (Not used, here to show I tried to implement it)
# class digit_tree_node:
#     def __init__(self, total = 0, recs = [], real_num):
#         self.value = total
#         self.records = recs
#         self.true_val = real_num
# 
#     def add_num(self, new_num):
#         addition = digit_tree_node(self.value+new_num)
# # #         

Answer 1

由于输入数字的范围是n < 10^6 ，输入的最大位数为 6。因此，最多有 5 个地方可以放置符号。所以，你可以试试蛮力法。 (实际上，在使用递归时，您确实在尝试蛮力(计算所有可能性))。

因此，您可以一次选择 0、1、2... 或 5 个位置来放置符号。

• 选择 0 个地方，即。输入数字 = 目标数字，例如。 (123,123)
• 选择一个位置，即 5C1(最大)和 4 种可能性。这样就有 20 种可能性。
• 现在，选择两个地方并尝试所有符号组合，(最多)5C2*4^2 = 160

同样，选择 3 个位置需要 640，选择 4 个位置需要 1280，所有 5 个位置需要 1024 种可能性。因此，最坏的情况是，您计算了大约 3000 种可能性(这是完全可行的)。

因此，为了选择放置符号的位置，请使用长度 = 输入长度的位掩码。然后，一旦你选择了，尝试所有的符号，计算它，如果它匹配，打印它和中提琴!!