пазл строка целых чисел

Question

Я прошу прощения за отсутствие математического фона, чтобы поставить этот вопрос более формально. Я ищу, чтобы создать строку из 796 букв (или целых чисел) с определенными свойствами.

По сути, строка является вариацией последовательности B Brujn (12,4), за исключением того, что не учитываются порядок и повторение в каждой подпоследовательности n-длины. т.е. ABBB BABA BBBA каждый эквивалентен {AB}. Другими словами, основное свойство строки включает в себя просмотр последовательных групп из 4 букв в большей строке (то есть с 1 по 4 буквы, со 2 по 5 буквы, с 3 по 6 буквы и т. д.) И затем создание набора букв, которые составляют каждую группу (повторы и порядок не учитываются)

Например, в строке из 9 букв:

A B B A C E B C D

первые 4-буквенные группы: ABBA, которая состоит из набора {AB} вторая группа: BBAC, которая состоит из набора {ABC} третья группа: BACE, которая состоит из набора {ABCE} и т.д.

Цель состоит в том, чтобы каждая комбинация из 1-4 букв из набора из N букв была представлена ​​1-4-буквенными результирующими наборами групп из 4 элементов один и только один раз в исходной строке.

Например, если используется набор из 5 букв {A, B, C, D, E} Тогда возможны 1-4 буквенные комбинации: A, B, C, D, E, AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE, BCDE

Вот рабочий пример, в котором используется набор из 5 букв {A, B, C, D, E}.

D D D D E C B B B B A E C C C C D A E E E E B D A A A C B D D B

Элементы с 1-го по 4-й образуют множество: D Элементы со 2-го по 5-й образуют набор: DE Элементы с 3-го по 6-й образуют набор: CDE Элементы с 4 по 7 образуют набор: BCDE Элементы с 5-го по 8-й образуют набор: BCE Элементы с 6-го по 9-й образуют набор: BC С 7-го по 10-й элементы образуют множество: B и т.д.

* Я надеюсь найти рабочий пример строки, которая использует 12 различных букв (всего 793 4-буквенные группы в 796-буквенной строке), начиная (и, если возможно, заканчивая) с 4 из то же письмо *

Вот рабочее решение на 7 букв:

AAAABCDBEAAACDECFAAADBFBACEAGAADEFBAGACDFBGCCCCDGEAFAGCBEEECGFFBFEGGGGFDEEEEFCBBBBGDCFFFFDAGBEGDDDDBE

Answer 1

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

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

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-я статья посвящена разбиению графа Де Брюина.

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

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

Answer 2

Классная проблема. Просто черновик / псевдо 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), чтобы доказать, что это жизнеспособный ответ ...

Answer 3

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

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

1. Начальный.Начните с результата k-1 и введите символы для синглетонов (уникальное расширение пустое пересечение):
   • ABCDE -> AABBCCDDEE
2. пометить использованную карту = 2 набора: AB, BC, CD, DE
3. Перезапись.Форма карты = 3 набора для ввода символов в отмеченную карту = 2.1-е выполнимое лексикографическое расширение срабатывает (возможно, придется вернуться для k> 2)
   • можно использовать уже отмеченные 2-е, поскольку все они будут заменены
   • , но, возможно, придется сделать проверкупройти для более высокого k
   • AB-> ACB, BC-> BCD, CD-> CED, DE-> DAE ==> AACBBDCCEDDAEEB
4. отметить / проверить использованные 2s
   • обычно сохраняют маркировку / снятие отметки во время строительства, но сохраняют старый список отметок
   • маркировка / снятие отметки может дорого обойтись, если в # 3
   • есть возврат: Не используется: AB, BE
5. Для более высокого k может потребоваться несколько рекурсивных проходов перезаписи
   • возможно разбиение новых наборов на классы
6. Завершение: не используется 2-s должны перекрываться по краю (вот почему это циклично) ABE - B может перейти к началу или и: AACBBDCCEDDAEEB

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

Я думал об этом и набрасываю решение.

Давайте назовем строку из четырех символов a word , и мы напишем S (w) для обозначения набора символов в слове w .

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

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

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

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

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

Код, которому нужно следовать после выходных, с небольшим количеством удачи ...