Алгоритм замены символов

Есть входящая строка из нескольких символов. заранее неизвестно как введены символы - на кириллице или латинице.

Нужен алгоритм который переберет все возможные варианты. Символы из заранее определенного словаря. Могут располагаться не подряд.

Например входящая строка АААА. И на выходе мы должны получить список из 16 вариантов написания.

Подскажите хотя-бы примерный алгоритм...