I have such piece of code:
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;
}
}
I have to get different combinations of chars from different elements. For example, if user prints 575, this piece of code will make 2D array {"jkl", "pqrs", "jkl"}. And after that I should also make 2D array with different combinations of letters, one letter from element (for example {"jpj", "jpk", "jpl", "krl"} etc). And the problem is with making these combinations. I don't understand how can I do that. It's also forbidden to work with dynamic memory (malloc, free, etc) and ready functions for sorting (qsort, lsearch, etc).
I tried to use nested loops and recursive but I don't know how to use it in this situation correctly. I'd be extremely grateful for any help, both theoretical or practical.
CodePudding user response：
Letter sets
The solution below uses only iteration. Getting the 2D array of the letter sets is fairly simple and uses the code you already have. An important detail to note is that if you what those letter sets to be printable, you need to account for the extra null termination character '\0'. Therefore, each row of the letter set array will contain the maximum number of letters 1, i.e. 4 1 characters.
Combinations array
To generate the combinations without dynamic array resizing, you will need to know how many combinations exists. This is calculated as the product of the number of letters of each set. So now, you can declare a static array with 1 row per combination and n 1 columns, one for each letter set plus the null-terminating character.
Representing a combination
Apart from the obvious letter-based way, a combination can be represented as a vector of indices, where the i-th index denotes the selected character from the i-th character set. Thus, the vector (0, 0, 2) represents the combination where the first character is taken from the first set, the first character is taken from the second set and the third character is taken from the third set.
With this index vector, it is easy to construct the respective string. The advantage is that it is also easy to generate the next combination as well! Starting from the last index, increment it if the resultant index is less than the size of the letter set. If so, then you have a new index vector representing a new unseen combination. If the resultant index exceeds the set size, then you need to set it to zero and apply this process to the next (towards the left) index of the vector until a valid increment is found.
Combinations order
You want all the combinations to be sorted. Notice that the letters in all sets are sorted. Thus the combinations themselves, following the procedure I described, will also be sorted, because you are exhaustively generating them from the last character to the first and the characters in each place are provided in lexicographic order. So there is no need to explicitly sort the result.
Note: in the code, for easy testing, I use a local variable arg to provide the input digits. Simply change that to take the input from 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: %s\n", 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] = '\0';
// 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("%s\n", combinations[i]);
}
return 0;
}