元件2D阵列C的组合

Question

我有这样一段代码：

for (int i = 0; argv[1][i]; i++) {
case '2':
strcpy(letters[i], "abc");
break;
case '3':
strcpy(letters[i], "def");
break;
case '4':
strcpy(letters[i], "def");
break;
case '5':
strcpy(letters[i], "jkl");
break;
case '6':
strcpy(letters[i], "mno");
break;
case '7':
strcpy(letters[i], "pqrs");
break;
case '8':
strcpy(letters[i], "tuv");
break;
case '9':
strcpy(letters[i], "wxyz");
break;
}
}

我必须从不同的元素中获得不同的字符组合。例如，如果用户打印575，则这段代码将生成2D阵列{"jkl"，"pqrs"，"jkl"}。在那之后，我还应该制作具有不同字母组合的2D数组，一个字母来自元素(例如{"jpj"、"jpk"、"jrl"、"krl"}等(。而问题在于如何进行这些组合。我不明白我怎么能那样做。还禁止使用动态内存(malloc、free等(和用于排序的就绪函数(qsort、lsearch等(。

我试着使用嵌套循环和递归，但我不知道如何在这种情况下正确使用它。我将非常感谢任何帮助，无论是理论上的还是实践上的。

Answer 1

字母集

下面的解决方案仅使用迭代。获取字母集的2D数组相当简单，并且使用了您现有的代码。需要注意的一个重要细节是，如果您将这些字母设置为可打印，则需要考虑额外的空终止字符''。因此，字母集数组的每一行将包含最大数量的字母+1，即4+1个字符。

组合阵列

要在不调整动态数组大小的情况下生成组合，您需要知道存在多少个组合。这是按每组字母数的乘积计算的。因此，现在，您可以声明一个静态数组，每个组合有1行，n+1列，每个字母集加上null终止字符一列。

表示组合

除了明显的基于字母的方式外，组合可以表示为索引的向量，其中第i个索引表示从第i个字符集中选择的字符。因此，向量(0, 0, 2)表示其中第一个字符取自第一集合、第一个字符选自第二集合以及第三个字符取自第三集合的组合。

使用这个索引向量，可以很容易地构造相应的字符串。其优点是也很容易生成下一个组合！从最后一个索引开始，如果得到的索引小于字母集的大小，则将其递增。如果是这样，那么您就有了一个新的索引向量，表示一个新看不见的组合。如果结果索引超过了设置的大小，则需要将其设置为零，并将此过程应用于向量的下一个(向左(索引，直到找到有效的增量。

组合订单

您希望对所有组合进行排序。请注意，所有集合中的字母都已排序。因此，按照我所描述的过程，组合本身也将被排序，因为您正在从最后一个字符到第一个字符进行详尽的生成和，每个地方的字符都是按字典顺序提供的。因此，没有必要显式地对结果进行排序。

注意：在代码中，为了便于测试，我使用局部变量arg来提供输入数字。只需将其更改为从argv[1]获取输入即可。

#include <stdio.h>
#include <string.h>
int main(){

char *arg = "575";

// Get length of argument (denotes number of letter sets)
int n = strlen(arg);
if (n == 0){
printf("No digits given");
return 0;
}

// Declare 2D array of letters (n rows, 5 columns)
char letters[n][5];

int total_combinations = 1;

// Fill array with characters
for (int i = 0; arg[i]; i++) {
switch(arg[i]){
case '2':
strcpy(letters[i], "abc");
break;
case '3':
strcpy(letters[i], "def");
break;
case '4':
strcpy(letters[i], "ghi");
break;
case '5':
strcpy(letters[i], "jkl");
break;
case '6':
strcpy(letters[i], "mno");
break;
case '7':
strcpy(letters[i], "pqrs");
break;
case '8':
strcpy(letters[i], "tuv");
break;
case '9':
strcpy(letters[i], "wxyz");
break;
}

total_combinations *= strlen(letters[i]);
}

// Print all letter sets
for (int i=0; i<n; i++){
printf("letters %d: %sn", i, letters[i]);
}

// Declare array of sorted combinations (total_combinations rows, n+1 columns)
// and an array keeping track of the current combination
char combinations[total_combinations][n+1];
int current_comb[n];

// Initialize current_comb to zeros
for (int i = 0; i < n; i++) current_comb[i] = 0;

// Generate all combinations
int k = 0;
while (k < total_combinations){
// Store current combination
for (int set_idx = 0; set_idx < n; set_idx++){
int letter_idx = current_comb[set_idx];
combinations[k][set_idx] = letters[set_idx][letter_idx];
}
// Null-terminate the string
combinations[k][n] = '';

// Generate next combination
// From the end of the combination indices
for (int i = n-1; i >= 0; i--){
// Increment index
current_comb[i]++;
// Set to zero if it exceeds the letters bounds, otherwise break out of the loop
if (current_comb[i] == strlen(letters[i])){
current_comb[i] = 0;
}
else {
break;
}
}

// Increment combinations count
k++;
}

// Print all combinations
for (int i=0; i<total_combinations; i++){
printf("%sn", combinations[i]);
}
return 0;
}