英文:
Using Permutations in Java for solving an equation
问题
对于给定的问题，我被赋予两个数字，它们将以如下方式相加得到特定结果：
num1 + num2 = result
然而，这些数字将被“编码”，因此，例如，一个输入可能是：
ab + bc = acd
这些数字的长度可以是最多9位数。
我的任务是创建一种有效的方法来找出每个输入有多少种可能的解，或者是否不可能有解。
我通过创建一个名为“Number”的类（在Java中），该类具有字母（char类型）和数值（int），然后将每个数字转换为这个新类Number的数组，这样我就可以轻松地检查它们的当前值。
然而，我不太确定如何解决这个回溯问题。
我知道我应该从number1和number2开始比较个位数，然后是十位数，依此类推，在每个“级别”中只选择和合适的情况，例如在上面的例子中，对于单位位，b=2 且 c=3，只有当 d=5 时才有意义，并且我可以排除所有对于这两个预先存在的值 d 不等于 5 的情况。
我被告知可以只使用两个循环来涵盖所有这些排列：一个循环用于遍历可能的数字[0到9]，另一个用于遍历所有的字母/变量，但我不太明白如何做到这一点！
如果我必须想象一下，我想我可以把它想象成
for 循环（从最右边的列向上到最短数字的最左边的列）
for 循环（数字从0到9？）
但我仍然无法理解这种方法，或者如何可以用递归来解决这个问题，非常感谢所有帮助，以提高我的理解力。
英文:
For a given problem I am granted with two numbers that will sum to a certain result in this way:
num1 + num2 = result
However these numbers will be "coded", so, for example, an input may be:
ab + bc = acd
The numbers can have any length up to 9 digits.
My task is to create an efficient method to find how many possible solutions each input has or if it is impossible.
I have tackled this issue by creating a class called Number (in java), that has a letter (char type) and a numeric value (int) and then I converted each number to an array of this new class Number, so I can easily check their current values.
However I'm not so sure how to approach this backtracking issue.
I am aware that I should start comparing the units from number1 and number2, then the tens, and so on, in each "level" selecting only the cases in which the sum will be logical, so for example in the above example for the units b=2 and c= 3 it would only make sense if d=5, and I could discard all the other cases in which d!= 5 for those two preexisting values.
I am told it is possible to cover all these permutations using only two cycles: One for cyclcing through the possible numbers [0 to 9] and one to cover all the letters/variables, but I don't quite understand how it could be done!
If I had to imagine it I guess I could think of it as
for cycle ( through "columns" from the rightmost up to the leftmost column of the shortest number)
for cycle( for numbers 0 to 9?)
but still I can't wrap my head around this approach to the subject, or how I could tackle this with recursion instead, all help to improve my understanding is very much appreciated.
答案1
得分: 1
这里有一个应该有效的算法。
让我们以你的例子方程式为例：
ab + bc = acd
-
确定方程式中唯一字符的数量。在你的例子中，有四个字符（a、b、c、d）。
-
为了遍历所有可能性，我们将设置一个循环。这个循环的最小值是 10^3 或 1,000。最大值是 10^4 或 10,000。方程式中唯一字符的数量决定了你将使用的 10 的幂次。最大值是 10^10，比一个
int还要大。一个long类型会适用。 -
在迭代中，将索引拆分为 N 个数字。在你的例子中，这将是 4 个数字。因为我们从 1,000 迭代到 9,999（包括 10,000 在内），所有索引值都将有 4 个数字。
-
检查确保这 N 个数字是唯一的，没有重复。这将在开始时消除大部分索引值。
-
将数字代入方程式并检查方程式是否有效。如果有效，将方程式保存在一个
List<String>中。 -
在完成迭代后，输出
List中的值或表示未找到解决方案。
英文:
Here's one algorithm that should work.
Let's take your example equation:
ab + bc = acd
-
Determine the number of unique characters in the equation. In your example, that would be four (a, b, c, d).
-
In order to iterate through all of the possibilities, we're going to set up a loop. The minimum value of this loop is 10 ^ 3 or 1,000. The maximum value of this loop is 10 ^ 4 or 10,000. The number of unique characters in the equation determines the powers of 10 you'll use. The maximum maximum is 10 ^ 10 which is bigger than an
int. Alongwould work. -
Inside the iteration, split the index into N digits. In your example, that would be 4 digits. Since we're iterating from 1,000 to 9,999 inclusive (10,000 excluded) all of the index values will have 4 digits.
-
Check to make sure the N digits are unique. No duplicates. This will eliminate most of the index values at the start.
-
Substitute the digits into the equation and check to see if the equation is valid. If so, save the equation in a
List<String>. -
Output the
Listvalues or no solution found after completing the iteration.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论