Добрый вечер!
Дана система текстовых замен:
1. |>∗< на >∗
2. d| на |md
3. dm на md
4. d> на >
5. <>∗< на
6. e| на e
7. em на |e
8. e> на >
Также дана строка (пример: <|>*<||>), для которой могут быть применены эти замены.
Задача заключается в том, чтобы построить все возможные цепочки действий, представленные в системе текстовых замен, над заданной строкой. В результате должны получить список всех последовательностей действий над строкой, например:
1224567678
1225467678
1225647678
1225674678
1225676478
1225676748
1252467678
1252647678
1252674678
1252676478
1252676748
1256247678
1256274678
1256276478
1256276748
1256724678
1256726478
1256726748
1522467678
Все последовательности должны быть оконченными, такие, что после выполнения данных действий нельзя было произвести никаких замен над строкой.
Я решил написать программу на питоне для реализации данной задачи и вот, что получилось:
s = '<|>*<||>'
arr_replacements = [
['|>*<', '>*<d'],
['d|', '|md'],
['dm', 'md'],
['d>', '>'],
['<>*<', '<e'],
['e|', 'e'],
['em', '|e'],
['e>', '>']
]
def recursive_replace(s, path):
k = 0
for i in range(len(arr_replacements)):
z = arr_replacements[i]
if (s != s.replace(z[0], z[1])):
path += str(i + 1)
s = s.replace(z[0], z[1])
return recursive_replace(s, path)
else:
k += 1
if k == len(arr_replacements):
return path
print(recursive_replace(s, str()))
Правда эта программа сейчас проходится только по одной ветке и собирает только одну последовательность. Пока не имею представления как её переделать, чтобы она перебирала все возможные варианты.
