Поиск максимальной цепочки в последовательности

#python #алгоритм

Имеется к примеру последовательность: [b,ab,bc,bb] из неё надо построить цепочку
вида: ab -> bb -> b -> bc (как понял вариант с b->bb тоже рабочий) и для этого я применял
сначала вот такой алгоритм:

def chains(words, previous_word_index=None):
   yield []
   if previous_word_index is not None:
       previous_letter = words[previous_word_index][-1]
       words = words[:previous_word_index] + words[previous_word_index + 1:]
   for i, each_word in enumerate( words ):
       if previous_word_index is None or each_word.startswith(previous_letter):
           for tail in chains(words, previous_word_index=i):
                yield [each_word] + tail  
print(max(chains(words), key=len))


потом пробовал использовать алгоритм по нахождению эйлерового пути, но там лишнее
выводило и я от него отказался.
Библиотечная функция networkx.dag_longest_path тоже не вариант тк в графе есть цикл
(b->bb, bb->b).

Есть вариант не рекурсивного алгоритма для поиска такой максимальной последовательности?

p.s. без полного перебора.

Ссылка на задачу с её полным описанием: 

atpp.vstu.edu.ru/cgi-bin/arh_problems.pl?id_prb=205

    

Ответы

Ответ 1

Прочитав внимательно и несколько раз условие, ставится понятно, что нужно искать
не максимальный путь, а именно полный путь. 

Если переформулировать условие. У нас есть граф, где вершины - {a..z} а ребро - слово
начинающееся на первую вершину и заканчивающееся на 2. (Да мультиграф, да есть петли).
Нам нужно найти Эйлеров путь. В целом можно уже ничего не писать, а давать ссылку
на википедию) Но вот код на С++ (быстро проверить идею). Основной код достаточно маленький

while (!st.empty()){
    int v = st.top();
    int i;
    for (i=0; i<26; ++i)
        if (G[v][i])
            break;
    if (i == 26){
        res.push_back (v);
        st.pop();
    }
    else {
        G[v][i]--;
        st.push (i);
    }
}


ссылка на запускаемый пример https://ideone.com/zvqa9m

Сложность не больше чем 26*N. (и то можно без 26, но это уже мелочи. успевает с диким
запасом).


Ответ 2

Можно что-то и получше придумать чем это:

import copy


class Item(object):
    def __init__(self, value, items):
        self.value = value
        self.next = self._get_next(items)

    def _get_next(self, items):
        return [item for item in items if self.value[-1] == item[0]]


def copy_dictionary(dictionary):
    return {key: copy.deepcopy(value) for key, value in dictionary.items()}


graph = {}
items = ['b', 'ab', 'bc', 'bb']

for index, item in enumerate(items):
    graph[item] = Item(item, items[:index] + items[index + 1:])

longest_path = []

for item in items:
    tmp_graph = copy_dictionary(graph)
    queue = [[tmp_graph[item]]]
    while queue:
        current_items = queue.pop(0)

        if not current_items[-1].next:
            if len(current_items) > len(longest_path):
                longest_path = current_items
            continue

        for next_item in current_items[-1].next:
            if tmp_graph[next_item].value in [current_item.value for current_item
in current_items]:
                continue
            queue.append(current_items + [tmp_graph[next_item]])


print(' -> '.join([item.value for item in longest_path]))  # 'ab -> b -> bb -> bc'


UPDATE: в предыдущих примерах делал интуитивно то же самое, что и @pavel, но к своему
стыду не знал про Эйлеров граф.

# матрица смежности графа (количество ребер, соединяющих вершины)
graph = [[0] * 26 for _ in range(26)]
# словарь (та же матрица смежности, только вместо количества ребер - массив слов)
dictionary = [[[] for __ in range(26)] for _ in range(26)]
# массив со степенями вершин
deg = [0] * 26
# последовательность слов
stack = []
# массив с индексами позиций слов
result = []

n = int(input())

# если задано всего одно слово, то сразу его и выводим
if n == 1:
    print(input())
else:
    for _ in range(n):
        word = input()
        # первый символ слова (исходящая вершина)
        first_char = ord(word[0]) - ord('a')
        # последний символ слова (входная вершина)
        last_char = ord(word[-1]) - ord('a')
        # увеличиваем количество ребер между этими вершинами
        graph[first_char][last_char] += 1
        # добавляем в словарь
        dictionary[first_char][last_char].append(word)
        # для исходящей вершины повышаем степень
        deg[first_char] += 1
        # для входной понижаем
        deg[last_char] -= 1

    # в результате тестового примера получится следующее:
    #   |  a  |      b      |  c     |
    # --+-----+-------------+--------|
    # a | [ ] | ['ab']      | [ ]    |
    # --+-----+-------------+--------|
    # b | [ ] | ['b', 'bb'] | ['bc'] |
    # --+-----+-------------+--------|
    # c | [ ] | [ ]         | [ ]    |
    # --+----------------------------|

    start = -1
    finish = -1

    # нужно найти подходящую вершину, 
    # с которой лучше начинать составлять последовательность слов
    for index in range(26):
        if deg[index] == 0:
            continue
        # подойдет та вершина, из которой исходящих ребер больше, чем входных
        # (в тестовом примере это 'ab', а 'bc' не подойдет - нет исходящих ребер)
        elif deg[index] == 1 and start == -1:
            start = index
        elif deg[index] == -1 and finish == -1:
            finish = index
        else:
            print('NO')
            exit(0)

    # если идеально подходящих для старта вершин нет, то начинаем по порядку
    if start == -1:
        start = 0

    stack.append(start)

    # обычный алгоритм поиска путей в графе
    while stack:
        vertex = stack[-1]
        index = 0

        while index < 26:
            if graph[vertex][index] > 0:
                break
            index += 1

        if index == 26:
            result.append(vertex)
            stack.pop()
        else:
            graph[vertex][index] -= 1
            stack.append(index)

    if len(result) - 1 != n:
        print('NO')
        exit(0)

    for index in range(len(result) - 1, 0, -1):
        print(dictionary[result[index]][result[index - 1]].pop(0))


Результат: данное решение прошло успешно все тесты.