Здравствуйте, korzh.pavel, Вы писали:

KP>Элементарные действия над симолами: поменять символы местами, переместить символ, удалить символ

Переводя на язык математики — удовлетворяет ли данному regexp'у любая перестановка любого подмножества данного множества символов? Так?

KP>Алгоритм должен выдать что то такое:
KP>поменять символы на второй и третей позиции

Что касается результата — он не однозначен
regexp: bca
string: abc
Поменять первый и второй, потом второй и третий?
Поменять второй и третий, потом первый и третий?
Переместить первый символ в конец?

Ясно, что последнее в каком-то смысле короче, но при более длинных строках будут иметь место множественные описания действий "одной длины".