将一个数字(0-9)添加到序列/字符串将创建新的4位数字

Question

我正在尝试找到一个算法，它可以通过键入键0-9来“打开保险箱”。代码长度为4位。保险箱将打开，它将代码标识为键入的子字符串。这意味着，如果代码是"3456“，那么下一次输入将打开保险箱："123456”。(这只是意味着保险箱不会每输入4个键就重新启动一次)。

是否有一种算法，每次向序列中添加一个数字时，都会创建新的4位数字(序列\字符串的最后4位数字的新组合)？

谢谢，km。

编辑(我在几年前发布的)：问题是如何确保每次我设置保险箱的输入(一位数)时，我会生成一个新的4位数代码，这是以前没有生成的。例如，如果保险箱得到3位数长度的二进制代码，则这应该是我的输入序列：

0001011100 

因为每次输入我都会得到一个新的代码(3位数长)，这是以前没有生成的：

000 -> 000
1 -> 001
0 -> 010
1 -> 101
1 -> 011
1 -> 111
0 -> 110
0 -> 100

Answer 1

我找到了解决你问题的方法：

让我们用以下方式定义有向图G= (V，E)：

V={代码的所有可能组合}。

E= {< u，v>|v可以从u中添加1位数字(在末尾)，并删除第一位数字}。

|V| = 10^4。

每个顶点的Din和Dout等于10 => |E| = 10^5。

你需要证明在G中存在Hamilton环-如果你这样做了，你就可以证明解的存在性。

EDIT1:

算法：

哈密尔顿循环- {v1，v2，..，vn-1，v1}。

• 按下v1中的每个数字。

• X <- v1。

• 当保险箱未打开时：

5.1 X <-哈密尔顿路径中X之后的下一个顶点。

5.2按X.中的最后一个数字

我们可以看到，因为我们使用了Hamilton循环，所以我们永远不会重复相同的子串。(最后4次按下)。

EDIT2:

当然，Hamilton路径就足够了。

Answer 2

这里总结一下我认为你正在尝试解决的问题，以及关于我可能如何解决它的一些解释。http://www.cs.swan.ac.uk/~csharold/cpp/SPAEcpp.pdf

然而，你必须做一些巧妙的处理，使其适合中国邮递员的问题。想象一下解决这个问题的二进制数字，三个数字的字符串。假设你有前两位数，并问问你自己，我有哪些选择来移动？(关于接下来的两位数字符串？)剩下的是一个有向图。

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

解决中国邮递员，你将有所有的组合，并将形成一个字符串现在的问题是，中国邮递员是可解的吗？对于CPP，有一些算法可以确定DAG是否是可解的，但我不知道这个特定的图是否一定是基于问题的可解性。这将是一件值得确定的事情。然而，你知道你可以从算法上找出它是否可解，如果是，你可以使用论文中提供的算法(我认为)和在线求解。

这里的每个顶点都有两条传入边和两条传出边。有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

Answer 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}

当你有一个已经在length=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}

我认为这不是一种非常复杂的方式来遍历给定序列的所有子序列。