Рекурсивный подход был бы простым способом здесь.
Давайте рассмотрим, что вы хотите сгенерировать все строки с m
буквами, все они разные, взятые из массива letters[m]
и чисел n
,это может быть повторено, взято из массива numbers[N]
(n
может быть меньше, такого же размера больше, чем N
, это не имеет значения).
Вы можете решить это таким образом (псевдокод, Стиль C):
void print_them_all(char *numbers, int nb_numbers_in_result, int n \
char *letters, bool *is_letter_used, int nb_letters_in_result, int m,
char *current_string){
if ((nb_numbers_in_result == n) && (nb_letters_in_result == m)){
// terminal case -> time to print the current string
printf("%s\n", current_string);
} else {
// string not completely built yet
// get the index where the next char will be added
current_index = nb_letters_in_result + nb_numbers_in_result;
if (nb_numbers_in_result < n){ // still possible to add a number
for (int i = 0; i < N; i++){
current_string[current_index] = numbers[i];
print_them_all(numbers, nb_numbers_in_result+1, n, \
letters, is_letter_used, nb_letters_in_result, m, \
current_string);
}
}
if (nb_letters_in_result < m){ // still possible to add a letter
for (int i = 0; i < m; i++) {
if (is_letter_used[i] == false){ // check the letter has not been added yet
// keep track that the letter has been added by 'marking' it
is_letter_used[i] = true;
// add it
current_string[i] = letters[i];
// recursive call
print_them_all(numbers, nb_numbers_in_result, n, \
letters, is_letter_used, nb_letters_in_result+1, m, \
current_string);
// now 'unmark' the letter
is_letter_used[i] = false;
}
}
}
}
}
Чтобы решить эту проблему, необходим рекурсивный подход.Это работает следующим образом:
, если у меня уже есть строка с k
числами, k<n
, тогда я могу добавить к ней любое число и продолжить (теперь моя строка будет иметь k+1
чисел вэто).
Если у меня уже есть строка с k
буквами, k<m
, тогда я могу добавить любую букву, которая еще не была добавлена (массив логических значений помогает убедиться, что это так),и я могу продолжить.Если моя строка готова к печати, выведите ее на печать.
Первый вызов должен быть выполнен с использованием логического массива, инициализированного везде: false
и 0
для значений nb_letters_in_result
и nb_numbers_in_result
,поскольку вы еще не добавили ни одной цифры или буквы в строку результата.
Что касается строки результата, поскольку вы кодируете в C, не забудьте выделить для нее память:
char *current_string = malloc((m+n+1) * sizeof(char));
иобнулить его:
current_string[m+n] = '\0';