如何获得等于 Python 中结果编号的列表的所有数学组合

Question

背景

我们有一个家庭传统，我和我兄弟姐妹的圣诞礼物是由一个代码识别的，这个代码只能使用与我们相关的数字来解决。例如，代码可以是 birth month * age + graduation year（这是一个简单的代码）。如果数字是8 * 22 + 2020 = 2196，我所有的圣诞礼物都会写上2196

我已经创建了一个 Python class，它为每个兄弟姐妹创建了一个列表，其中包含与他们相关的每个数字。目前该列表有 30 多个号码，但可能会增加到 40 多个。

问题

是否有任何方法可以测试等于结果数字的数字列表的所有数学组合？例如，findPossibleCombinations( [8, 7, 4, 22, 2020, 573], 2196 ) returns 一个列表列表可以创建结果编号？所以这个函数会 return [8, 22, 2020] 和它发现的任何其他列表可以用来等于 2196。没有数字会被使用超过一次。

我确定有一种方法可以实现 O(N^47) 算法（当然是开玩笑），但我想知道实现这种结果的最优化算法是什么？

为了节省计算时间，将操作数限制为总共 5-6 次。我的 parents 并不疯狂，可能永远不会使用超过 5-6 个数字来计算最终结果。我还将操作限制为 +、-、* 和 /，尽管我可能需要在未来几年添加其他操作。

感谢您的所有帮助！我希望你至少能从我奇怪的家庭传统中笑出来。

编辑：这是我的 class 结构。它可以优化更多，但现在已经足够好了。任何字符串都被转换为字母数字和反字母数字，并按字母添加。 “listofnums”是我要使用的列表。

def getalpha( str, inverse ):
   "Converts string to alphanumeric array of chars"
   array = []
   for i in range(0, len(str)): 
      alpha = ord(str[i]) - 96
      if inverse:
        array.append(27 - alpha)
      else:
        array.append(alpha)
   return array;

class Person:
  def __init__(self, name, middlename, birthmonth, birthday, birthyear, age, orderofbirth, gradyear, state, zip):
    #final list
    self.listofnums = []
    self.listofnums.extend((birthmonth, birthday, birthyear, birthyear - 1900, age, orderofbirth, gradyear, gradyear - 2000, zip))
    letters = name + middlename + state
    #add all related alphanumeric letters
    self.listofnums.extend(getalpha(letters, False))
    self.listofnums.extend(getalpha(letters, True))

Answer 1

你需要itertools.product。它给出了一个生成器，该生成器生成给定序列的笛卡尔积的所有元组。

from itertools import product

values1 = range(3)     # replace with your candidate birth month values
values2 = range(3, 6)  # replace with your candidate age values
values3 = range(7, 9)  # replace with your candidate graduation year values 
target_values = {10, 20, 30}  # replace with your target values (results)
# target_values need to be a set for efficient lookup.
for val1, val2, val3 in product(values1, values2, values3):
    if val1 + val2 + val3 in target_values:  #replace with your function
        print(val1, val2, val3)

Answer 2

Ismael 的反应很好，让我走上了正确的道路。我必须将所有操作的排列与所有数字的组合结合起来，以获得将达到目标值中的数字的所有可能集合（数字列表和操作列表）的列表。

这个答案确实假定一个常数来定义解决方案中的操作数

#Master algorithm (Get the result set of all combinations of numbers and cartesian products of operations that reach a target_value, using only the number_of_numbers_in_solution)
#Example: sibling1.results[1] = [(3, 22, 4), (<built-in function add>, <built-in function add>), 29]. This means that 3 + 22 + 4 = 29, and 29 is in target_values

NUMBER_OF_OPERATIONS_IN_SOLUTION = 3
NUMBER_OF_NUMBERS_IN_SOLUTION = NUMBER_OF_OPERATIONS_IN_SOLUTION + 1
TARGET_VALUES = {22,27,29,38,39}

import operator
from itertools import product
from itertools import combinations

def getresults( list ):
  #Add the cartesian product of all possible operations to a variable ops
  ops = []
  opslist = [operator.add, operator.sub, operator.mul, operator.truediv]
  for val in product(opslist, repeat=NUMBER_OF_OPERATIONS_IN_SOLUTION):
    ops.append(val)

  #Get the result set of all combinations of numbers and cartesian products of operations that reach a target_value
  results = []
  for x in combinations(list, NUMBER_OF_NUMBERS_IN_SOLUTION):
      for y in ops:
          result = 0
          for z in range(len(y)):
              #On the first iteration, do the operation on the first two numbers (x[z] and x[z+1])
              if (z == 0):
                  result = y[z](x[z], x[z+1])
              #For all other iterations, do the operation on the current result and x[z+1])
              else:
                  result = y[z](result, x[z+1])
      if result in TARGET_VALUES:
          results.append([x, y, result])
  print(len(results))
  return results

如何获得等于 Python 中结果编号的列表的所有数学组合

How to get all mathematical combinations of a list that equal a result number in Python

python

algorithm

math

combinations