找出所有可能的数字组合
Find all possible combinations of numbers
背景（TL;DR – 原文post）
我目前正在努力解决 C 中的这个问题，我想知道是否有人知道该怎么做。我需要打印所有可能的解决方案来解决像 BASE + BALL = GAMES 这样的密码问题。例如这里的一个解决方案是：A=4 B=7 E=3 G=1 L=5 S=8 M=9 对应于 7483 +7455= 14938。所以我的任务是找到正确的数字到字符映射这是真的。我可以使用 0-9 的数字，每个数字只能分配给一个字母。该解决方案需要递归顺便说一句。我的思考过程是从 3 个字符串中找到所有唯一字符并为它们分配一个数字，然后检查上述关系的解决方案是否为真。如果这不是真的，我需要尝试不同的数字与字符组合。我只是不知道我需要用什么方法来涵盖所有可能的组合。我不一定想要代码，我只是想找人向我解释开始它的算法逻辑或提供任何可能的资源。
编辑：我所说的密码算术问题是指用户输入 3 个字符串来创建类似 SEND + MORE = MONEY 的等式的问题。这个等式是通过为每个字母分配一个从 0-9 的唯一数字来求解的，就像我在上面的例子中展示的那样。
所以我们想要一个程序来做这样的事情：
输入：s1 = 发送，s2 =“更多”，s3 =“金钱”
输出：一种可能的解决方案是：
D=1 E=5 M=0 N=3 O=8 R=2 S=7 Y=6
如果您尝试用分配给它的数字替换每个字符，您会发现所创建的等式成立。我需要一个程序来做到这一点，这意味着找到数字到字符的正确映射，以便生成的等式是正确的。
真题
实际问题只是寻找可能的数字到字母的分配，而不是解决一般的密码难题。它是：
How to generate all variations of length k from the set of ten single-digit non-negative numbers?
换句话说，找到所有长度为 k（对于某些 0 < k ≤ 10）的整数序列 0 到 9，序列中没有重复数字。
你问的是数学问题而不是程序员问题。
这可能是您要搜索的公式。
(N_a*10^n + ... + B_a*10^1 + A_a*10^0)
+ (N_b*10^n + ... + B_b*10^1 + A_b*10^0)
----------------------------------------
= (N_c*10^n + ... + B_c*10^1 + A_c*10^0)
因此，在您的“BASE + BALL = GAMES”示例中，公式如下：
(B*10^3 + A*10^2 + S*10^1 + E*10^0)
+ (B*10^3 + A*10^2 + L*10^1 + L*10^0)
----------------------------------------------
= (G*10^4 + A*10^3 + M*10^2 + E*10^1 + S*10^0)
这是一个有 7 个未知数的线性方程。
下面的词也可以写成：
(B*10^3 + A*10^2 + S*10^1 + E*10^0)
+ (B*10^3 + A*10^2 + L*10^1 + L*10^0)
-------------------------------------------------
= (2*B*10^3 + 2*A*10^2 + (S+L)*10^1 + (E+L)*10^0)
导致：
2*B*10^3 + 2*A*10^2 + (S+L)*10^1 + (E+L)*10^0 = G*10^4 + A*10^3 + M*10^2 + E*10^1 + S*10^0
对于所有可能的术语，最简单的解决方案是：
A=0, B=0, E=0, G=0, L=0, S=0, M=0
但我想，这不是您要找的。
另一个非常重要的事实是，所有未知数必须是从0到9的自然数，[0, 9]。但正如我所展示的，您在使用 0 时需要仔细查看，因为这可能会产生不需要的结果。
所以也许只查找从 1 到 9 的所有自然数，[1, 9]。
PS 了解数字运算算法
PPS 一个非常愚蠢的算法是：
int number_crunching = 1;
int A = B = E = G = L = S = M = 1;
while(number_crunching == 1){
if(B*2000 + A*200 + (S+L)*10 + E + L == G*10000 + A*1000 + M*100 + E*10 + S)
{
number_crunching = 0; //found a solution
break;
}
if(++A == 10){
A = 1;
if(++B == 10){
B = 1;
if(++E == 10){
E = 1;
if(++G == 10){
G = 1;
if(++L == 10){
L = 1;
if(++S == 10){
S = 1;
if(++M == 10){
number_crunching = -1; //found no solution
break;
}
}
}
}
}
}
}
}
PPPS 我没有测试循环，但你现在应该知道如何尝试解决你的问题
基于your comment 我了解到您现在对输入数据分析不感兴趣，即识别问题中有多少个不同的字母（自变量），也不代表它们在方程式中的位置求解，或一种测试 one-digit 数字对这些变量的赋值是否满足方程的方法。
您只需寻找一种方法来找到所有可能的 one-digit 数字分配给这些变量。
因此，允许使用多个数字 n=10 并使用多个不同的字母（解决方案中的变量）k 您需要找到
- 要分配的所有 C(n,k) 位数字组合，并且
- 对于每个组合，它的所有 k！排列，即分配给 letters/variables.
的不同顺序
可能找到这些组合和排列的最有效方法是递归的。然而，这会让你在递归的底部深入调用下一阶段，并且代码会很难理解。所以我更喜欢效率较低但更易读的迭代方法。
让我们声明一个要分配给变量的值数组。我们事先不知道需要多少个变量，但肯定不会超过 10 个（因为问题定义了一个约束条件，即每个变量（字母）都被分配了一个不同的数字，并且最多有 10 个不同的数字可以分配).所以：
int values[10];
现在，让我们创建第一个组合。它将由第一个可能的 k 数字组成，即 0 到 k-1:
void FirstCombination(int values[], int k)
{
for (int i = 0; i < k; i++)
values[i] = i;
}
我们必须从当前组合创建一个新组合。通常这可以通过简单地增加最后一个数字来完成。它将修改选定的序列，例如：
2, 3, 7 → 2, 3, 8
但是，如果最后一个值已经是 9，会发生什么呢？
2, 3, 9 → 2, 3, ???
好吧，我们可以检查 one-but-last 值是否可以递增（这意味着它小于 8），如果可以递增，则将最后一个值设置为比该值大一:
2, 3, 9 → 2, 3 → 2, 4 → 2, 4, 5
这显然归结为第一个元素：
2,7,8,9 → 2 → 3 → 3,4,5,6
如果成功，我们 return 一个 'true' 值 (1) 表明我们找到了一个新的有效组合，否则（none 值可以递增）我们return 'false' (0):
int NextCombination(int values[], int n, int k)
{
for (int i = k-1; i >= 0; i--) // from the last number backwards
{
if (values[i] < n + i - k) // can this be incremented?
{
values[i] ++; // increment
while (++i < k) // reset following values
values[i] = values[i - 1] + 1;
return 1;
}
}
return 0;
}
然后我们可以用一个简单的循环遍历所有组合：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
//
// ... process the combination here ...
//
} while (NextCombination(values, n, k));
这两个函数的一个方便的特点是每个交付的组合都是按升序给出的。
现在让我们看看如何构建给定数组的所有排列。以升序排列组合为我们以字典序 ('alphabetic') 顺序生成它们提供了一个良好的开端，这可以理解为由生成的数字序列生成的 'numbers' 本身按升序排列。例如，
2, 4, 5
2, 5, 4
4, 2, 5
4, 5, 2
5, 2, 4
5, 4, 2
为了实现这一点，让我们找到序列的递减尾部。如果它是整个序列，我们有最后一个排列（按字典顺序），所以我们完成了。否则，我们取尾部之前的数字并将其与尾部的下一个更大的项目交换。然后我们反转尾巴。以下是一些示例：
sequence tail next grtr exchange reverse result
1 3 5 6 7 1 3 5 6[7] 1 3 5 6<7> 1 3 5 7[6] 1 3 5 7[6] 1 3 5 7 6
1 5 7 6 3 1 5[7 6 3] 1 5 7<6>3 1 6[7 5 3] 1 6[3 5 7] 1 6 3 5 7
7 6 5 3 1 [7 6 5 3 1] none none [1 3 5 6 7] 1 3 5 6 7 DONE
这样我们最终恢复了第一个排列，这是继续搜索下一个组合的方便点。
int NextPermutation(int values[], int k)
{
// find the tail beginning
int tail = k-1;
while (tail > 0 && values[tail-1] > values[tail])
tail --;
// not the last permutation?
if (tail > 0)
{
int nextGreater = k - 1;
while (values[nextGreater] < values[tail - 1])
nextGreater --;
// found; now swap
int tmp = values[tail - 1];
values[tail - 1] = values[nextGreater];
values[nextGreater] = tmp;
}
// reverse the tail
int left = tail, right = k - 1;
while (left < right)
{
int tmp = values[left];
values[left] = values[right];
values[right] = tmp;
left ++; right --;
}
return tail > 0; // return 'true' if it wasn't the last permutation
}
现在我们可以使用两个嵌套循环遍历所有组合及其排列：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
do {
//
// ... process the permutation here ...
//
} while (NextPermutation(values, k));
} while (NextCombination(values, n, k));
或者，由于布尔运算符评估的 short-circuit 方法，具有复合条件的单个循环：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
//
// ... process the permutation here ...
//
} while (NextPermutation(values, k) || NextCombination(values, n, k));
看到它在 godbolt.org 工作：https://godbolt.org/z/YKe8s69qT
在循环内，您需要通过将 values 应用于相应的字母来评估三个输入表达式，然后验证相等性是否成立。在评估输入密码时，请注意可以多次应用相同的值，例如 BASEBALL.
中的两个 B、两个 A 和两个 L
还有一个您没有提到的额外困难：密码谜题通常假定零不能指定为前导数字。例如，15+8=23 是 AB+C=DE 的有效解，但 07+5=12 不是。所以你应该知道这三个词中哪些字母被用作首字母，而不是处理将零分配给其中任何一个的排列。
背景（TL;DR – 原文post）
我目前正在努力解决 C 中的这个问题，我想知道是否有人知道该怎么做。我需要打印所有可能的解决方案来解决像 BASE + BALL = GAMES 这样的密码问题。例如这里的一个解决方案是：A=4 B=7 E=3 G=1 L=5 S=8 M=9 对应于 7483 +7455= 14938。所以我的任务是找到正确的数字到字符映射这是真的。我可以使用 0-9 的数字，每个数字只能分配给一个字母。该解决方案需要递归顺便说一句。我的思考过程是从 3 个字符串中找到所有唯一字符并为它们分配一个数字，然后检查上述关系的解决方案是否为真。如果这不是真的，我需要尝试不同的数字与字符组合。我只是不知道我需要用什么方法来涵盖所有可能的组合。我不一定想要代码，我只是想找人向我解释开始它的算法逻辑或提供任何可能的资源。
编辑：我所说的密码算术问题是指用户输入 3 个字符串来创建类似 SEND + MORE = MONEY 的等式的问题。这个等式是通过为每个字母分配一个从 0-9 的唯一数字来求解的，就像我在上面的例子中展示的那样。
所以我们想要一个程序来做这样的事情：
输入：s1 = 发送，s2 =“更多”，s3 =“金钱”
输出：一种可能的解决方案是：
D=1 E=5 M=0 N=3 O=8 R=2 S=7 Y=6
如果您尝试用分配给它的数字替换每个字符，您会发现所创建的等式成立。我需要一个程序来做到这一点，这意味着找到数字到字符的正确映射，以便生成的等式是正确的。
真题
实际问题只是寻找可能的数字到字母的分配，而不是解决一般的密码难题。它是：
How to generate all variations of length
kfrom the set of ten single-digit non-negative numbers?
换句话说，找到所有长度为 k（对于某些 0 < k ≤ 10）的整数序列 0 到 9，序列中没有重复数字。
你问的是数学问题而不是程序员问题。
这可能是您要搜索的公式。
(N_a*10^n + ... + B_a*10^1 + A_a*10^0)
+ (N_b*10^n + ... + B_b*10^1 + A_b*10^0)
----------------------------------------
= (N_c*10^n + ... + B_c*10^1 + A_c*10^0)
因此，在您的“BASE + BALL = GAMES”示例中，公式如下：
(B*10^3 + A*10^2 + S*10^1 + E*10^0)
+ (B*10^3 + A*10^2 + L*10^1 + L*10^0)
----------------------------------------------
= (G*10^4 + A*10^3 + M*10^2 + E*10^1 + S*10^0)
这是一个有 7 个未知数的线性方程。
下面的词也可以写成：
(B*10^3 + A*10^2 + S*10^1 + E*10^0)
+ (B*10^3 + A*10^2 + L*10^1 + L*10^0)
-------------------------------------------------
= (2*B*10^3 + 2*A*10^2 + (S+L)*10^1 + (E+L)*10^0)
导致：
2*B*10^3 + 2*A*10^2 + (S+L)*10^1 + (E+L)*10^0 = G*10^4 + A*10^3 + M*10^2 + E*10^1 + S*10^0
对于所有可能的术语，最简单的解决方案是：
A=0, B=0, E=0, G=0, L=0, S=0, M=0
但我想，这不是您要找的。
另一个非常重要的事实是，所有未知数必须是从0到9的自然数，[0, 9]。但正如我所展示的，您在使用 0 时需要仔细查看，因为这可能会产生不需要的结果。
所以也许只查找从 1 到 9 的所有自然数，[1, 9]。
PS 了解数字运算算法
PPS 一个非常愚蠢的算法是：
int number_crunching = 1;
int A = B = E = G = L = S = M = 1;
while(number_crunching == 1){
if(B*2000 + A*200 + (S+L)*10 + E + L == G*10000 + A*1000 + M*100 + E*10 + S)
{
number_crunching = 0; //found a solution
break;
}
if(++A == 10){
A = 1;
if(++B == 10){
B = 1;
if(++E == 10){
E = 1;
if(++G == 10){
G = 1;
if(++L == 10){
L = 1;
if(++S == 10){
S = 1;
if(++M == 10){
number_crunching = -1; //found no solution
break;
}
}
}
}
}
}
}
}
PPPS 我没有测试循环，但你现在应该知道如何尝试解决你的问题
基于your comment 我了解到您现在对输入数据分析不感兴趣，即识别问题中有多少个不同的字母（自变量），也不代表它们在方程式中的位置求解，或一种测试 one-digit 数字对这些变量的赋值是否满足方程的方法。
您只需寻找一种方法来找到所有可能的 one-digit 数字分配给这些变量。
因此，允许使用多个数字 n=10 并使用多个不同的字母（解决方案中的变量）k 您需要找到
- 要分配的所有 C(n,k) 位数字组合，并且
- 对于每个组合，它的所有 k！排列，即分配给 letters/variables. 的不同顺序
可能找到这些组合和排列的最有效方法是递归的。然而，这会让你在递归的底部深入调用下一阶段，并且代码会很难理解。所以我更喜欢效率较低但更易读的迭代方法。
让我们声明一个要分配给变量的值数组。我们事先不知道需要多少个变量，但肯定不会超过 10 个（因为问题定义了一个约束条件，即每个变量（字母）都被分配了一个不同的数字，并且最多有 10 个不同的数字可以分配).所以：
int values[10];
现在，让我们创建第一个组合。它将由第一个可能的 k 数字组成，即 0 到 k-1:
void FirstCombination(int values[], int k)
{
for (int i = 0; i < k; i++)
values[i] = i;
}
我们必须从当前组合创建一个新组合。通常这可以通过简单地增加最后一个数字来完成。它将修改选定的序列，例如：
2, 3, 7 → 2, 3, 8
但是，如果最后一个值已经是 9，会发生什么呢？
2, 3, 9 → 2, 3, ???
好吧，我们可以检查 one-but-last 值是否可以递增（这意味着它小于 8），如果可以递增，则将最后一个值设置为比该值大一:
2, 3, 9 → 2, 3 → 2, 4 → 2, 4, 5
这显然归结为第一个元素：
2,7,8,9 → 2 → 3 → 3,4,5,6
如果成功，我们 return 一个 'true' 值 (1) 表明我们找到了一个新的有效组合，否则（none 值可以递增）我们return 'false' (0):
int NextCombination(int values[], int n, int k)
{
for (int i = k-1; i >= 0; i--) // from the last number backwards
{
if (values[i] < n + i - k) // can this be incremented?
{
values[i] ++; // increment
while (++i < k) // reset following values
values[i] = values[i - 1] + 1;
return 1;
}
}
return 0;
}
然后我们可以用一个简单的循环遍历所有组合：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
//
// ... process the combination here ...
//
} while (NextCombination(values, n, k));
这两个函数的一个方便的特点是每个交付的组合都是按升序给出的。
现在让我们看看如何构建给定数组的所有排列。以升序排列组合为我们以字典序 ('alphabetic') 顺序生成它们提供了一个良好的开端，这可以理解为由生成的数字序列生成的 'numbers' 本身按升序排列。例如，
2, 4, 5
2, 5, 4
4, 2, 5
4, 5, 2
5, 2, 4
5, 4, 2
为了实现这一点，让我们找到序列的递减尾部。如果它是整个序列，我们有最后一个排列（按字典顺序），所以我们完成了。否则，我们取尾部之前的数字并将其与尾部的下一个更大的项目交换。然后我们反转尾巴。以下是一些示例：
sequence tail next grtr exchange reverse result
1 3 5 6 7 1 3 5 6[7] 1 3 5 6<7> 1 3 5 7[6] 1 3 5 7[6] 1 3 5 7 6
1 5 7 6 3 1 5[7 6 3] 1 5 7<6>3 1 6[7 5 3] 1 6[3 5 7] 1 6 3 5 7
7 6 5 3 1 [7 6 5 3 1] none none [1 3 5 6 7] 1 3 5 6 7 DONE
这样我们最终恢复了第一个排列，这是继续搜索下一个组合的方便点。
int NextPermutation(int values[], int k)
{
// find the tail beginning
int tail = k-1;
while (tail > 0 && values[tail-1] > values[tail])
tail --;
// not the last permutation?
if (tail > 0)
{
int nextGreater = k - 1;
while (values[nextGreater] < values[tail - 1])
nextGreater --;
// found; now swap
int tmp = values[tail - 1];
values[tail - 1] = values[nextGreater];
values[nextGreater] = tmp;
}
// reverse the tail
int left = tail, right = k - 1;
while (left < right)
{
int tmp = values[left];
values[left] = values[right];
values[right] = tmp;
left ++; right --;
}
return tail > 0; // return 'true' if it wasn't the last permutation
}
现在我们可以使用两个嵌套循环遍历所有组合及其排列：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
do {
//
// ... process the permutation here ...
//
} while (NextPermutation(values, k));
} while (NextCombination(values, n, k));
或者，由于布尔运算符评估的 short-circuit 方法，具有复合条件的单个循环：
int n = 10;
int values[10];
FirstCombination(values, k);
do {
//
// ... process the permutation here ...
//
} while (NextPermutation(values, k) || NextCombination(values, n, k));
看到它在 godbolt.org 工作：https://godbolt.org/z/YKe8s69qT
在循环内，您需要通过将 values 应用于相应的字母来评估三个输入表达式，然后验证相等性是否成立。在评估输入密码时，请注意可以多次应用相同的值，例如 BASEBALL.
B、两个 A 和两个 L
还有一个您没有提到的额外困难：密码谜题通常假定零不能指定为前导数字。例如，15+8=23 是 AB+C=DE 的有效解，但 07+5=12 不是。所以你应该知道这三个词中哪些字母被用作首字母，而不是处理将零分配给其中任何一个的排列。