Добавление одной цифры (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
 TheZ03 июл. 2012 г., 21:34
Какой язык? Платформа? Брось нам кость.
 KernelMode03 июл. 2012 г., 21:42
@Thez, в точности как «gbtimmon» отметил, что это не имеет значения. Я ищу абстрактную идею. (хотя решение в коде совсем не плохо)
 alfasin03 июл. 2012 г., 21:35
не можете "просто вспомнить" последние 3 символа?
 gbtimmon03 июл. 2012 г., 21:45
@ Thez, я думаю, что это чисто алгоритмический вопрос, который означает, что платформа и язык будут спорными. Я думаю, что он спрашивает, как генерировать каждую 4-значную комбинацию, написав одну строку и не повторяя 4-значных комбинаций. Примером решения из 3 цифр с номерами 0-1 может быть «1000101110». Это очень интересный вопрос. Это какая-то проблема программирования acm?
 gbtimmon03 июл. 2012 г., 22:48
@alfasin Я думаю, что вопрос в том, что вы должны создать одну последовательность, которая содержит каждое 4-значное число в качестве подпоследовательности, но не содержит 4-значную подпоследовательность дважды. поэтому последовательность 123451234 будет недопустимой, поскольку она содержит 1234 дважды.

Ответы на вопрос(3)

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

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, вам не нужно продолжать объединение, просто удалите 1-ю цифру последовательности и вставьте новую цифру в конце, например, используйте последний элемент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}

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

 04 июл. 2012 г., 00:42
@ gbtimmon ты прав! в последовательности / подпоследовательности порядок действительно имеет значение (и это было моим намерением). У меня сложилось впечатление, что проблема не очень хорошо определена. У меня сложилось впечатление, что мы говорим о последовательности и подпоследовательности из-за его последнего предложения:(new combinations of the last 4 digits of the sequence\string)?
 03 июл. 2012 г., 22:32
Как вы тогда производите одну строку из этого? И это не последовательность ....en.wikipedia.org/wiki/Sequence, Вы производите Подмножества набора длиной 4 изset чисел 1-9. Есть гораздо более простой способ сделать это, и это не решает проблему. Разница в последовательности, порядок важен, в наборе это не так, и, поскольку вы переставляете порядок в своем примере, вы не смотрите на подпоследовательность. Хорошее размышление, хотя, мне нравится видеть людей, пытающихся решить сложные проблемы
Решение Вопроса

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

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

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

| V | = 10 ^ 4.

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

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

EDIT1:

Алгоритм:

Construct directed graph G as mentioned above.

Calculate Hamilton cycle - {v1,v2,..,vn-1,v1}.

Press every number in v1.

X <- v1.

while the safe isn't open:

5.1 X <- next vertex in the Hamilton path after X.

5.2 press the last digit in X.

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

EDIT2:

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

 03 июл. 2012 г., 22:13
@alfasin Я имел в виду все возможные комбинации в длину 4. Цикл Гамильтона именно то, что ему нужно.
 03 июл. 2012 г., 22:16
Я понял, что ты сказал. и я говорю, что нам не нужно проверятьall комбинации, толькоsub-sequences
 03 июл. 2012 г., 22:11
это неall possible combinations - толькоsub sequence of the typing если я правильно понял
 23 янв. 2013 г., 16:33
 KernelMode03 июл. 2012 г., 22:16
Спасибо, это хорошее направление. Но теперь проблема в том, что у нас недостаточно ребер на узел (Diracкаждая вершина имеет степень n / 2 или больше. Мы не делаем). Но доказательство того, что граф является Гамильтоном, абсолютно решит его существование решения.

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

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

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

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

Каждая вершина здесь имеет 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
 KernelMode04 июл. 2012 г., 21:29
Благодарю. Я бы проверил статью в первую очередь.

Ваш ответ на вопрос