Часть 5. Буквометика

[Все темы по перестановкам]

Литература: Кнут. Том 4. Выпуск 2. Генерация всех картежей и перестановок. 2008

Задача: Футбол и математика

Описание решение:
Суть задачи решить ребус аналогичный такому:
                        MOTOR
                  +      FIAT 
                       ------
                        VOLVO
Где вместо букв нужно поставить цифру. При этом разные буквы должны иметь разные цифровые значения.
По условию задачи количество различных букв не превосходит 10.
Значит в общем случае нужно перебрать все размещения без повторений для n=10(10 цифр) и k = количеству различных букв в ребусе. А в худшем случае – 10! различных перестановок.
Генерация размещений без повторений имеет схожую природу с генерацией перестановок без повторений. Поэтому данная задача попала в блок к перестановкам.

Алгоритм будет иметь следующую структуру:
1) Получение строки, содержащей все различные буквы исходного ребуса в порядке слева направо, сверху вниз. Для примера это будет строка “MOTRFIAVL”.
1) Генерация текущего размещения без повторений для заданных n и k в лексикографическом порядке.
2) Т.к. длина текущего размещения равна длине строке различных букв из п.1), проинициализировать i-ую букву i-ым значением размещения.
3) Проверка корректности ребуса.
4) Если возможно, перейти на п. 1).

Реализация:
В самом решении использовалась рекурсивная схема, схожая со схемой генерации всех перестановок без повторений.
Обратите внимание на изящную реализацию считывания(ст.4):

1. void input()
2. {
3.   char a[12],b[12],c[12];
4.   scanf("%[A-Z]+%[A-Z]=%[A-Z]",&a,&b,&c);
5.   A = string(a); B = string(b); C = string(c);
6. }

* This source code was highlighted with Source Code Highlighter.

[Решение]

P.S: Метод ветвей и границ для данной задачи.