Способ, которым я хотел бы сделать это, состоит в том, чтобы создать массив индексов той же длины, что и строка, все инициализированные в нуле.Затем мы рассматриваем этот массив индексов как счетчик для перечисления всех возможных отображений нашей исходной строки.Индекс 0 отображает эту позицию в строке на первое сопоставление для этого символа, 1 на второй и т. Д. Мы можем пройти их по порядку, просто увеличив последний индекс в массиве, перенося его на следующую позицию, когда мыдостичь максимального числа отображений для этой позиции.
Чтобы использовать ваш пример, у нас есть отображения
'a' => 'e', 'o'
'b' => 'i'
Со входной строкой "abba" нам нужен массив из четырех элементов для нашегоindexes:
[0,0,0,0] => "abba"
[0,0,0,1] => "abbe"
[0,0,0,2] => "abbo"
[0,0,1,0] => "abia"
[0,0,1,1] => "abie"
[0,0,1,2] => "abio"
[0,1,0,0] => "aiba"
[0,1,0,1] => "aibe"
[0,1,0,2] => "aibo"
[0,1,1,0] => "aiia"
[0,1,1,1] => "aiie"
[0,1,1,2] => "aiio"
[1,0,0,0] => "ebba"
[1,0,0,1] => "ebbe"
[1,0,0,2] => "ebbo"
[1,0,1,0] => "ebia"
[1,0,1,1] => "ebie"
[1,0,1,2] => "ebio"
[1,1,0,0] => "eiba"
[1,1,0,1] => "eibe"
[1,1,0,2] => "eibo"
[1,1,1,0] => "eiia"
[1,1,1,1] => "eiie"
[1,1,1,2] => "eiio"
[2,0,0,0] => "obba"
[2,0,0,1] => "obbe"
[2,0,0,2] => "obbo"
[2,0,1,0] => "obia"
[2,0,1,1] => "obie"
[2,0,1,2] => "obio"
[2,1,0,0] => "oiba"
[2,1,0,1] => "oibe"
[2,1,0,2] => "oibo"
[2,1,1,0] => "oiia"
[2,1,1,1] => "oiie"
[2,1,1,2] => "oiio"
Прежде чем мы начнем генерировать эти строки, нам понадобится где-то их хранить, что в C означает, что нам нужно будет выделить память.К счастью, мы уже знаем длину этих строк, и мы можем определить количество строк, которые мы собираемся сгенерировать - это просто произведение количества отображений для каждой позиции.
Хотя вы можете вернуть их в массиве , я предпочитаю использовать обратный вызов, чтобы вернуть их, когда я их найду.
#include <string.h>
#include <stdlib.h>
int each_combination(
char const * source,
char const * mappings[256],
int (*callback)(char const *, void *),
void * thunk
) {
if (mappings == NULL || source == NULL || callback == NULL )
{
return -1;
}
else
{
size_t i;
int rv;
size_t num_mappings[256] = {0};
size_t const source_len = strlen(source);
size_t * const counter = calloc( source_len, sizeof(size_t) );
char * const scratch = strdup( source );
if ( scratch == NULL || counter == NULL )
{
rv = -1;
goto done;
}
/* cache the number of mappings for each char */
for (i = 0; i < 256; i++)
num_mappings[i] = 1 + (mappings[i] ? strlen(mappings[i]) : 0);
/* pass each combination to the callback */
do {
rv = callback(scratch, thunk);
if (rv != 0) goto done;
/* increment the counter */
for (i = 0; i < source_len; i++)
{
counter[i]++;
if (counter[i] == num_mappings[(unsigned char) source[i]])
{
/* carry to the next position */
counter[i] = 0;
scratch[i] = source[i];
continue;
}
/* use the next mapping for this character */
scratch[i] = mappings[(unsigned char) source[i]][counter[i]-1];
break;
}
} while(i < source_len);
done:
if (scratch) free(scratch);
if (counter) free(counter);
return rv;
}
}
#include <stdio.h>
int print_each( char const * s, void * name)
{
printf("%s:%s\n", (char const *) name, s);
return 0;
}
int main(int argc, char ** argv)
{
char const * mappings[256] = { NULL };
mappings[(unsigned char) 'a'] = "eo";
mappings[(unsigned char) 'b'] = "i";
each_combination( "abba", mappings, print_each, (void *) "abba");
each_combination( "baobab", mappings, print_each, (void *) "baobab");
return 0;
}