algorithm - 重组数等于数学公式

Question

我一直在考虑一个数学/算法问题，希望你能提供一些关于如何解决它的建议！
如果我有一个数字（例如479），我想将它的数字或它们的组合重新组合成与原始数字匹配的数学公式。所有数字都应按其原始顺序使用，但可以组合成数字（因此，479允许4、7、9、47、79），但每个数字只能使用一次，因此不能有像4x47x9这样的数字，因为现在数字4使用了两次。
现在举个例子来说明我是怎么想的。这个例子在数学上是不正确的，因为我不能给出一个实际可行的好例子，但它演示了输入和预期输出。
示例输入：29485235
示例输出：2x9+48/523^5
正如我所说的，我的例子没有加起来（2x9+48/523^5不会产生29485235），但我想知道是否有一种算法能真正让我找到这样一个公式，由源数的数字按其原始顺序组成，在计算时会产生原始数。
在使用的数学类型上，我会说括号（）和add/sub/mul/div/pow/sqrt。
有什么办法吗？我的想法是简单的暴力强迫它通过随机分割数字和做计算，希望得到一个匹配的结果。但总有更好的办法吧？
编辑：如果在非原始顺序中更容易，或者你有一个解决这个问题的想法，而忽略了上面描述的一些“条件”，那么理解如何解决这样的问题仍然会有很大帮助。

Answer 1

对于大约6位数的数字，我认为应该按照以下方案强制执行：
1）将初始值分成一个数字列表（数组，不管怎样，根据语言）。最初，这些是数字。
2）对于每对数字，使用其中一个运算符将它们组合在一起。如果结果是目标号码，则返回success（并打印出在离开时执行的所有操作）。否则，如果它是一个整数，则在新的更小的列表中递归，该列表由刚刚计算的数字和未使用的数字组成。或者您可能希望允许非整数中间结果，这将使搜索空间更大一些。二进制操作是：
添加
减去
乘
分
权力
连接（只能用于原始数字或通过连接产生的数字）。
3）允许平方根将搜索空间膨胀到无穷大，因为它是一元运算符。所以你需要一种方法来限制它的应用次数，我不确定会是什么（随着答案接近1，可能会失去精确性？）。这是只允许整数中间值的另一个原因。
4）指数运算会迅速导致溢出。2^（9^（4^8））太大，无法直接存储所有数字（尽管在基2中，它们是什么是非常明显的；-））。因此，要么你不得不承认你可能会错过具有大中间值的解，要么你必须编写一堆代码来计算因子。这些显然与加法的交互效果不太好，所以您可能需要做一些估计。例如，通过观察因子数量的大小，我们发现2^（9^（4^8））离（2^35）很远，所以不需要计算（2^（9^（4^8））+5）/（2^35）。它不可能是29485235，即使它是一个整数（当然不是-另一种排除这个特殊例子的方法）。我认为处理这些数字比其他问题加在一起要困难，所以也许你应该限制自己从一个数字的幂开始，也许应该限制在64位整数中的结果，这取决于你使用的语言。
5）我忘记排除任何输入的琐碎解决方案，只需连接所有数字。不过，这很容易处理，只需通过递归来维护一个参数，该参数告诉您是否在到当前子问题的路由上执行了任何非连接操作。如果你没有，那么忽略错误的匹配。
我对6位数的估计是基于这样一个事实，即编写一个Countdown求解器相当容易，即使在没有解的情况下，它也能在几秒钟内运行。这个问题的不同之处在于，数字必须按顺序使用，但有更多的操作（倒计时不允许指数运算、平方根运算、串联运算或非整数中间结果）。总的来说，我认为这个问题是可比较的，只要你解决平方根和溢出问题。如果你能在几秒钟内解决一个案子，那么你可以在合理的时间内强行通过一百万个候选人（假设你不介意让你的电脑开着）。
10位数字，暴力似乎是不可能的，因为你必须考虑100亿个案例，每个案例都需要大量的递归。所以我想你会在两者之间达到暴力的极限。
还要注意，我在顶部的简单算法仍然有很多冗余——它不会停止你做（4,7,9,1）—>（47,9,1）—>（47,91），然后再做（4,7,9,1）—>（4,7,91）—>（47,91）。所以，除非你弄清楚这些重复将在哪里发生并避免它们，否则你将尝试（47,91）两次。显然，当列表中只有2个数字时，这并不是什么大工作，但是当列表中有7个数字时，您可能不希望以6种不同的方式将其中的4个数字相加，然后6次解决结果中的4个数字问题。倒计时游戏不需要聪明，但据我所知，在这个问题上，它可能会造成暴力逼迫8位数字和暴力逼迫9位数字之间的差异，这是相当重要的。