Добавление одной цифры (0-9) к последовательности / строке создает новый 4-значный номер

Я пытаюсь найти алгоритм, который "ломает сейф", набирая ключи 0-9. Код состоит из 4 цифр. Сейф будет открыт, где он идентифицирует код как подстроку набора текста. Это означает, что если код "3456", то при следующем наборе будет открыт сейф: "123456". (Это просто означает, что сейф не перезапускается через каждые 4 нажатия клавиш).

Существует ли алгоритм, который каждый раз, когда он добавляет одну цифру в последовательность, создает новый номер из 4 цифр (новые комбинации последних 4 цифр последовательности \ строки)?

спасибо км

Редактирование (я отправляю это несколько лет назад): Вопрос в том, чтобы убедиться, что каждый раз, когда я устанавливаю ввод (одну цифру) в сейф, я генерирую новый 4-значный код, который не был сгенерирован ранее. Например, если сейф получает двоичный код длиной 3 цифры, то это должна быть моя входная последовательность:

0001011100

Потому что для каждого ввода я получаю новый код (длиной 3 цифры), который не был сгенерирован ранее:

000 -> 000
1 -> 001
0 -> 010
1 -> 101
1 -> 011
1 -> 111
0 -> 110
0 -> 100
Источник

3 ответа

Решение

Я нашел сокращение вашей проблемы:

Определим ориентированный граф G = (V,E) следующим образом:

V = {все возможные комбинации кода}.

E = { | v можно получить от u, добавив 1 цифру (в конце) и удалив первую цифру}.

| V | = 10 ^ 4.

Din и Dout каждой вершины, равной 10 => |E| = 10^5.

Вам нужно доказать, что в G есть цикл Гамильтона - если вы это сделаете, вы можете доказать существование решения.

EDIT1:

Алгоритм:

  1. Построить ориентированный граф G, как указано выше.

  2. Вычислить цикл Гамильтона - {v1,v2,..,vn-1,v1}.

  3. Нажмите каждый номер в v1.

  4. X <- v1.

  5. пока сейф не открыт:

    5.1 X <- следующая вершина на пути Гамильтона после X.

    5.2 нажмите последнюю цифру в X.

Мы можем видеть, что, поскольку мы используем цикл Гамильтона, мы никогда не повторяем одну и ту же подстроку. (Последние 4 нажатия).

EDIT2:

Конечно пути Гамильтона достаточно.

Источник

Вкратце, вот проблема, которую, я думаю, вы пытаетесь решить, и некоторые объяснения того, как я могу подойти к ее решению. http://www.cs.swan.ac.uk/~csharold/cpp/SPAEcpp.pdf

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

 /-\
/   V    
\-  00 ----> 01
      ^  /   ^|
       \/    ||
       /\    ||
      V  \   |V
 /-- 11 ---> 10 
 \   ^         
  \-/

Решите китайский почтальон, у вас будут все комбинации и вы получите одну строку. Вопрос в том, разрешим ли китайский почтальон? Существуют алгоритмы, которые определяют погоду или нет, DAG разрешима для CPP, но я не знаю, является ли этот конкретный график обязательно разрешимым, основываясь только на проблеме. Это было бы хорошо, чтобы определить. Тем не менее, вы знаете, что вы можете выяснить, алгоритмически ли она решаема, и если это так, вы можете решить ее, используя алгоритмы, доступные в этой статье (я думаю) и онлайн.

Каждая вершина здесь имеет 2 входящих ребра и 2 исходящих ребра. Есть 4 (2^2) вершины.

В полноразмерной задаче есть 19683( 3 ^ 9 ) вершины и каждая вершина имеет 512 ( 2 ^ 9 ) выходящие и входящие вершины. Там будет в общей сложности

19683( 3 ^ 9 ) x 512 (2 ^ 9) = 10077696 edges in your graph.

Подход к решению:

1.) Create list of all 3 digit numbers 000 to 999.
2.) Create edges for all numbers such that last two digits of first number match first
two digits of next number. 

ie 123 -> 238 (valid edge) 123 -> 128 (invalid edge)

3.) use Chinese Postman solving algorithmic approaches to discover if solvable and
solve
Источник

Я хотел бы создать массив подпоследовательностей, которые должны быть обновлены при любой вставке новой цифры. Итак, в вашем примере это будет выглядеть так:

array = {1}

затем

array = {1,2,12}

затем

array = {1,2,12,3,13,23,123}

затем

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234}

и когда у вас есть последовательность, которая уже имеет длину =4, вам не нужно продолжать объединение, просто удалите первую цифру последовательности и вставьте новую цифру в конце, например, используйте последний элемент 1234когда мы добавим 5 это станет 2345 следующее:

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234,5,15,25,125,35,135,235,1235,45,145,245,1245,345,1345,2345,2345}

Я полагаю, что это не очень сложный способ прохождения всех подпоследовательностей данной последовательности.

Источник
Другие вопросы по тегам