Как вычислить de Последовательности Брёйна для алфавитов без степени двойки?
Я пытаюсь вычислить последовательности де Брейна для алфавитов, которые имеют количество символов, равное не степень двойки.
Для алфавитов с 2 ^ k символами вычисление последовательностей де Брейна несложно: есть несколько простых правил, таких как «Предпочитать одно» и «Предпочитать противоположности» , которые работают для генерации B (2, n). B (2 ^ k, n) в точности совпадает с B (2, kn), если вы читаете единицы и нули как двоичные коды для фактических символов в вашем алфавите. Например, вы можете интерпретировать B (2,8n) как последовательность байтов длиной более n.
Prefer Ones довольно просто: напишите n нулей. Затем всегда записывайте единицу, если это не вызовет повторение строки длиной n; в противном случае напишите ноль.
В настоящее время я не вижу, как обобщить такие правила на алфавиты, не являющиеся степенями двойки.
Существует общий метод вычисления последовательностей де Брейна с помощью графов: пусть каждый последовательность длины n, сгенерированная вашим алфавитом, будет узлом; поместите ребро из A в B, если и только если крайние правые n-1 символы A совпадают с крайними левыми n-1 символами B. Обозначьте каждое ребро последним символом строки в головной вершине. Любой эйлеров путь через этот граф будет генерировать последовательность де Брейна, а использованная нами особенная конструкция гарантирует, что будет хотя бы один такой путь. Мы можем использовать алгоритм Флери , чтобы (недетерминированно) построить эйлеров путь:
- Выберите вершину.
- Оставьте эту вершину через некоторое ребро и удалите это ребро, выбрав только те ребра, удаление которых разъединит вершину из графа, если нет альтернативы.
- Добавьте к своей строке метку ребра, которое вы только что удалили.
- Перейти к 2, пока не исчезнут все ребра.
Результирующая строка будет последовательностью де Брейна.
Этот алгоритм несколько сложнее реализовать, чем алгоритм Prefer Ones. Простота Prefer Ones состоит в том, что нужно только просмотреть уже сгенерированный вывод, чтобы определить, что делать. Есть ли простой способ обобщить Prefer Ones (или, возможно, Prefer Opposites) на алфавиты размера, отличного от степени двойки?