Цепочка целых головоломок

Ответ 1

Остерегайтесь того, что для попытки исчерпывающего поиска (ответ в VB пытается получить наивную версию) вам сначала придется решить проблему генерации всех возможных расширений при сохранении лексикографического порядка. Просто ABC, расширяется до всех перехватов AABC, плюс все переполнения ABBC, плюс все переполнения ABCC, что составляет 3 * 4! а не просто AABC. Если вы просто конкатенируете AABC и AABD, это будет всего 4 из 4! perms of AABC и даже это случайно. Просто это расширение принесет вам экспоненциальную сложность - конец игры. Кроме того, вам необходимо поддерживать связь между всеми объяснениями и набором (набор становится меткой).

Лучше всего использовать один из известных эффективных конструкторов De Bruijn и попытаться выяснить, можете ли вы разместить свою эквивалентность в нем. Проверьте

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.674&rep=rep1&type=pdf

и

http://www.dim.uchile.cl/~emoreno/publicaciones/FINALES/copyrighted/IPL05-De_Bruijn_sequences_and_De_Bruijn_graphs_for_a_general_language.pdf

для начала.

Если вы знаете графики, другой жизнеспособный вариант - начать с графа Де Бройна и сформулировать свою эквивалентность набора как переписывание графа. В 2-й работе выполняется разбиение графа De Bruijn.

Кстати, попробуйте ответить VB только для A, B, AB (по крайней мере, расширение мало) - он сделает AABBAB и построит ABBA или ABBAB (или выложит достойный язык), оба из которых ошибочны. Вы даже можете доказать, что он всегда будет пропустить с 1-м лексическим расширением (то, что AAB, AAAB и т.д.), Просто изучив первые 2 прохода (он всегда будет пропускать 2-й A для NxA, потому что (N-1) xA + B находится в string (1-е расширение {AB}).

О, и если бы мы могли установить, сколько из каждого письма должно быть у оптимального солотона (не смотрите на B (5,2), это слишком легко и регулярно:-) будет случайным. (например, AAAA, BBBB... присутствуют и не касаются и имеют n1 As, n2 Bs...) и случайную компоновку, а затем проверяют, являются ли они решениями (в этом случае проверка выполняется намного быстрее, чем исчерпывающий поиск).

Ответ 2

Холодная проблема. Просто проект /psuedo algo:

dim STR-A as string = getall(ABCDEFGHIJKL) 
//custom function to generate concat list of all 793 4-char combos.
//should be listed side-by-side to form 3172 character-long string.
//different ordering may ultimately produce different results.
//brute-forcing all orders of combos is too much work (793! is a big #).
//need to determine how to find optimal ordering, for this particular
//approach below.
dim STR-B as string = "" // to hold the string you're searching for  
dim STR-C as string = "" // to hold the sub-string you are searching in  
dim STR-A-NEW as string = "" //variable to hold your new string
dim MATCH as boolean = false //variable to hold matching status

while len(STR-A) > 0 
//check each character in STR-A, which will be shorted by 1 char on each
//pass.
  MATCH = false
  STR-B = left(STR-A, 4)
  STR-B = reduce(STR-B) 
  //reduce(str) is a custom re-usable function to sort & remove duplicates

  for i as integer = 1 to len((STR-A) - 1)
    STR-C = substr(STR-A, i, 4) 
    //gives you the 4-character sequence beginning at position i
    STR-C = reduce(STR-C)
    IF STR-B = STR-C Then
       MATCH = true
       exit for 
       //as long as there is even one match, you can throw-away the first 
       //letter
    END IF
    i = i+1
  next


  IF match = false then 
  //if you didn't find a match, then the first letter should be saved
     STR-A-NEW += LEFT(STR-B, 1)
  END IF

  MATCH = false //re-init MATCH
  STR-A = RIGHT(STR-A, LEN(STR-A) - 1) //re-init STR_A
wend

В любом случае, могут возникнуть проблемы, и вам нужно будет написать еще одну функцию для анализа вашей строки результата (STR-A-NEW), чтобы доказать, что это жизнеспособный ответ...

Ответ 3

Я думал об этом, и я набросал решение.

Назовем строку из четырех символов словом, и мы напишем S (w), чтобы обозначить множество символов в слове w.

Каждое слово abcd имеет "последующие" слова bcde, где a,..., e - все символы.

Пусть succ (w) - множество последующих слов v для w таких, что S (w)!= S (v). succ (w) - это набор слов-преемников, которые могут следовать от первого символа в w, если w находится в решении.

Для каждого непустого набора символов s мощностью не более четырех слов (s) есть множество слов w таких, что S (w) = s. Любое решение должно содержать ровно одно слово в словах (s) для каждого такого множества s.

Теперь мы можем сделать разумный поиск. Основная идея такова: скажем, мы изучаем путь поиска, заканчивающийся словом w. Следующее слово должно быть не исключенным словом в succ (w). Слово v исключается, если путь поиска содержит некоторое слово w такое, что v в словах (S (w)).

Вы можете быть немного более хитрым: если мы будем отслеживать возможные слова "предшественника" множеству s (т.е. слова w с преемником v, такие как v в словах) и достигнуть точки, где каждый предшественник s исключается, то мы знаем, что мы зашли в тупик, так как мы никогда не сможем получить s из любого расширения текущего пути поиска.

Код, который следует после выходных, немного удачи...

Ответ 4

Вот мое предложение. Я соглашусь, что это производительность и память.

Это может быть излишним, но иметь класс. Мы будем называть его UniqueCombination. Это будет содержать уникальную комбинацию из 4 (w980) набора входных данных (то есть A, AB, ABC,...). Это также будет содержат список возможных комбинаций (AB (AABB, ABAB, BBAA,...)), для этого потребуется метод, который определяет, будет ли любая возможная комбинация перекрываться с любой возможной комбинацией другой UniqueCombination тремя символами. Также необходимо переопределение, которое также принимает строку.

Затем мы начинаем со строки "AAAA", затем находим все уникальные комбинации, которые перекрывают эту строку. Затем мы находим, сколько уникальных комбинаций совпадают с возможными совпадениями. (мы могли бы быть умными в этой точке хранить это число.) Затем мы выбираем тот, у которого наименьшее количество перекрытий больше 0. Используйте сначала наименее возможные совпадения.

Затем мы найдем конкретную комбинацию для выбранного UniqueCombination и добавим ее в финальную строку. Удалите эту уникальную комбинацию из списка, затем, когда мы найдем совпадения для текущей строки. промыть и повторить. (мы могли бы быть умными и в последующих прогонах при поиске перекрытий мы могли бы удалить любую из нередуцированных комбинаций, которые содержатся в финальной строке.)

Хорошо, что мой план я буду работать над кодом в эти выходные. Разумеется, это не гарантирует, что последние 4 символа будут 4 одинаковой буквы (на самом деле это можно было бы избежать, но я также рассмотрю это.)

Ответ 5

Если вообще существует неэкспоненциальное решение, его, возможно, нужно сформулировать в терминах рекурсивного "роста" из задачи с меньшим размером, т.е. для конструирования B (N, k) из B (N-1, k-1) или из B (N-1, k) или из B (N, k-1).

Систематическая конструкция для B (5,2) - один шаг в то время:-) Он связан с более сложным последним [карта обозначает мощность, {AB} имеет card = 2, я также буду называть их 2- s, 3-s и т.д.] Обратите внимание, что 2-х и 3-й будут k-1 и k последним (я надеюсь).

• Initial. Начните с результата k-1 и введите символы для одиночных чисел (единственное расширение пустое пересечение):
  • ABCDE → AABBCCDDEE
• mark used card = 2 набора: AB, BC, CD, DE
• Rewriting. Форма карты = 3 набора для ввода символов в отмеченную карту = 2. 1-е возможное лексикографическое расширение (возможно, потребуется отменить для k > 2)
  • ОК, чтобы использовать уже отмеченные 2-х с тех пор, как все они будут заменены.
  • но, возможно, придется выполнить проверку для более высокого k
  • AB- > ACB, BC- > BCD, CD- > CED, DE- > DAE == > AACBBDCCEDDAEEB
• mark/verify used 2s
  • обычно сохраняют маркировку/разметку во время строительства, но также сохраняют старые список отметок
  • Маркировка/разметка могут стать дорогостоящими, если в # 3 вернуться
  • Не используется: AB, BE
• Для более высоких k может потребоваться несколько рекурсивных переписывающих проходов
  • возможно разбиение новых наборов на классы
• Завершение: неиспользуемые 2-х должны перекрываться по краю (почему он цикличен)    ABE-B может перейти к началу или или: AACBBDCCEDDAEEB

Примечание: для шага от B (N-1, k) до B (N, k) может потребоваться инъекция псевдосигналов, таких как удвоение или триплекс A

B (5,2) → B (5,3) - B (5,4)

• Initial. то же: - ABCDE → AAACBBBDCCCEDDDAEEEB
• не использовать маркировку 3-х наборов, так как все они будут помечены
• Rewriting.
  • выберите систематические позиции вставки
    • AAA_CBBB_DCCC_EDDD_AEEE_B
  • отметьте все 2-е, выпущенные следующим образом: AC, AD, BD, BE, CE
  • использовать отмеченные 2-х для определения вставленных символов - общая регулярность тотальности:
    • AxCB D → ADCB
    • BxDC E → BEDC
    • CxED A → CAED
    • DxAE B = > DBAE
    • ExBA C → ECBA
• Убедитесь, что все 3-х используются (помечены вставленные символы только для удовольствия)
  • ААА [D] CBBB [Е] DCCC [А] EDDD [В] AEEE [С] В

Примечание: систематический выбор, если точка ввода детерминистически продиктована вставками (только AD может соответствовать 1-му, AC создаст дубликат 2-набора (AAC, ACC))

Примечание. Это не будет так хорошо для B (6,2) и B (6,3), так как число 2-s будет превышать 2x без 1-го. Это важно, так как 2-й сидит, естественно, по бокам 1-го типа, как CBBBE, и проблема заключается в том, как разместить их, когда вы закончите с 1-го уровня.

• B (5,3) настолько симметричен, что только повторение # 1 дает B (5.4):
  • AAAADCBBBBEDCCCCAEDDDDBAEEEECB