Ответ 1
Ниже приведен код Python для поиска кратчайшего возможного сокращения. Он нерекурсивный, но не слишком далеко от наивного алгоритма. На каждом шаге он пробует все возможные однократные сокращения, таким образом, получая набор строк для уменьшения для следующего шага.
Одна оптимизация, которая помогает в случаях, когда есть правила "употребления символа", такие как "aa" → "a", - это проверка следующего набора строк для дубликатов.
Еще одна оптимизация (не реализована в коде ниже) заключалась в том, чтобы обработать правила замены в конечном автомате, который находит местоположения всех возможных одиночных сокращений с одним проходом через входную строку. Однако это не помогло бы экспоненциальному характеру алгоритма поиска основного дерева.
class Replacer:
def __init__(self, replacements):
self.replacements = [[tuple(key), tuple(value)] for key, value in replacements.items()]
def get_possible_replacements(self, input):
"Return all possible variations where a single replacement was done to the input"
result = []
for replace_what, replace_with in self.replacements:
#print replace_what, replace_with
for p in range(1 + len(input) - len(replace_what)):
if input[p : p + len(replace_what)] == replace_what:
input_copy = list(input[:])
input_copy[p : p + len(replace_what)] = replace_with
result.append(tuple(input_copy))
return result
def get_minimum_sequence_list(self, input):
"Return the shortest irreducible sequence that can be obtained from the given input"
irreducible = []
to_reduce = [tuple(input)]
to_reduce_new = []
step = 1
while to_reduce:
print "Reduction step", step, ", number of candidates to reduce:", len(to_reduce)
step += 1
for current_input in to_reduce:
reductions = self.get_possible_replacements(current_input)
if not reductions:
irreducible.append(current_input)
else:
to_reduce_new += reductions
to_reduce = set(to_reduce_new[:]) # This dramatically reduces the tree width by removing duplicates
to_reduce_new = []
irreducible_sorted = sorted(set(irreducible), key = lambda x: len(x))
#print "".join(input), "could be reduced to any of", ["".join(x) for x in irreducible_sorted]
return irreducible_sorted[0]
def get_minimum_sequence(self, input):
return "".join(self.get_minimum_sequence_list(list(input)))
input = "aaaaa"
replacements = {
"aaba" : "a",
"aaa" : "ab",
"aba" : "bb",
}
replacer = Replacer(replacements)
replaced = replacer.get_minimum_sequence(input)
print "The shortest string", input, "could be reduced to is", replaced