安卓的点密码系统的熵是多少?

这只是一个部分答案。唯一相关的起始点是1、2和5。对于点1和2,您可以通过简单的旋转变换生成一个相当于从任何其他点(而不是5)开始的图案。这意味着,如果您可以枚举从1和2开始的所有模式,那么您可以通过乘以4来计算从5以外的任何数字开始的所有模式。

从5开始的路径是另一种情况。您可以通过计算以5->1和5->2开头的所有路径并乘以4来计算所有这些路径,因为您可以通过简单的旋转转换再次生成所有其他可能的路径。

所以,枚举路径的方法是…

(所有从1开始的路径+所有从2开始的路径+所有从5->1开始的路径+所有从5->2开始的路径)*4

同样,编号系统,便于参考:

1  2  3
4  5  6
7  8  9

对于第一步:

从1-gt;2、4、5、6和8可以访问。

从2->1、3、4、5、6、7和9可以访问(基本上不是8或其本身)。

从5->1、2、3、4、6、7、8和9可以访问。

之后的动作会变得非常有趣。

例如,1537是有效的密码。1539不是。

这里简明扼要地说,规则是:

路径中不能有两次点。如果一个点不是路径的一部分,并且正好被一个转换所交叉,那么它就成为源点和目标点之间的路径的一部分。

以下是一些示例路径:

• 允许2->3->1->8。
• 不允许1->3->2->5,因为当1->3正好超过2时,2不是路径的一部分,因此无论您是否希望,路径都将变为1->2->3->5。
• 不允许使用1->2->3->7,因为3->7交叉于5,5不是路径的一部分。
• 允许1->5->3->7。在3->7中忽略5,因为它已经是路径的一部分。

这个程序:

class LockPattern(object):
    def __init__(self, *args):
        if (len(args) == 1) and hasattr(args[0], '__iter__'):
            args = tuple(args[0])
        if len(args) > 9:
            raise TypeError("A LockPattern may have at most 9 elements.")
        self._pattern = ()
        for move in args:
            if not self.isValidNextStep(move):
                raise TypeError("%r is not a valid lock sequence." % (args,))
            else:
                self._pattern = self._pattern + (move,)
    def __len__(self):
        return len(self._pattern)
    def __iter__(self):
        return iter(self._pattern)
    def isValidNextStep(self, nextdot):
        nextdot = int(nextdot)
        if (nextdot < 1) or (nextdot > 9):
            raise ValueError("A lock sequence may only contain values from 1 "
                             "to 9 and %d isn't." % (nextdot,))
        if len(self._pattern) <= 0:
            return True # Any dot is valid for the first dot
        if len(self._pattern) >= 9:
            return False
        if nextdot in self._pattern:
            return False # No dot may be visited twice
        prevdot = self._pattern[-1]
        dotpair = tuple(sorted((prevdot, nextdot)))
        if dotpair == (1,3):
            return 2 in self._pattern
        if dotpair == (1,7):
            return 4 in self._pattern
        if dotpair in ((1,9),(2,8),(3,7),(4,6)):
            return 5 in self._pattern
        if dotpair == (3,9):
            return 6 in self._pattern
        if dotpair == (7,9):
            return 8 in self._pattern
        return True
    def isValidLockSequence(self):
        return 4 <= len(self)
    def newSequenceAddDot(self, nextdot):
        if not self.isValidNextStep(nextdot):
            raise ValueError("%d is not a valid next dot for the sequence." % (nextdot,))
        newseq = LockPattern()
        newseq._pattern = self._pattern + (nextdot,)
        return newseq

def genAllPatterns(starting = LockPattern()):
    if starting.isValidLockSequence():
        yield starting
    for dot in xrange(1,10):
        if starting.isValidNextStep(dot):
            for result in genAllPatterns(starting.newSequenceAddDot(dot)):
                yield result

print reduce(lambda x, p: x+1, genAllPatterns(), 0)

生成389112的答案。

它也验证了我以前的直觉:

lsts = tuple(((p, list(genAllPatterns(LockPattern(p)))) for p in ((1,), (2,), (5,1), (5,2))))
[(x[0], len(x[1])) for x in lsts]
-> [((1,), 38042), ((2,), 43176), ((5, 1), 7352), ((5, 2), 8708)]
sum((len(x[1]) for x in lsts)
-> 97278
97278 * 4
-> 389112

关键是要注意,一旦你访问了任意两个点,你就可以到达你想要的任何其他点,而无需移动任何你还没有访问过的点。因此,一旦您选择了两个起始点(按顺序),那么您就可以随意选择密码的其余部分,以您希望的任何顺序。(这是因为“骑士的动作”是允许的,至少根据你链接的页面)

因此,除了“起始两个”点,其余2-7位数字的尾数是7p2+7p3+7p4+7p5+7p6+7p7。有56个潜在的开始两位数的头部,因为有5个移动你可以从任何一个角点,7个从任何边缘点,8个从中心点。因此解锁模式总数为56*(7p2+7p3+7p4+7p5+7p6+7p7)=766752。

如果这是错误的,可能是因为我对这个系统的规则缺少一些知识。

好吧,首先让我先说,无所不能似乎是正确的。我们能用数学做什么?当他说确实只有3件事要处理时,我同意他的看法。1,2和5。

运营商想要一些优雅的计算公式,对于这样的问题,我怀疑是否存在。当你使用所有9个点的时候,你会发现哈密顿路径,如果这是一个完整的图,那就很容易计算了(事实并非如此)。因为这三个案例中的每一个都是唯一的,所以您将枚举所有案例,以便找到路径总数。

让我们看看第一个案例,从一个角落开始。一个角有四种选择,下一个角有五种选择。现在你会很快看到我们的公式扩展得相当快,因为我们有5个选择,我们必须将这5个选择分成2组。

移动到中间的正方形,无论您移动到哪个正方形,都将有相同的选择。相对于移动到5这将给我们更多的选择,我们的公式是:

4*(4*(6)+1*(7))

然后我们必须将6个和7个选项分成更多的组。如果我们移动到一个边正方形,那么我们现在可以移动到两个边正方形,三个角和一个中间正方形。然后我们的公式变成:

4*(4*(2*(5)+3*(3)+1*(7))+1*(7))

然后我们必须开始解决,如果我们搬到中间广场,我就停在这里。找到哈密顿路径是NP完全的,尽管我们只是计算它们。但是这里没有任何我们可以利用的优雅解决方案的属性。这是一个图论问题,也是一个涉及到暴力强迫解决方案的问题,就像之前由全神贯注者所做的那样。

我试着解释为什么你的直觉是错误的,你说:

“我知道事实上,解决这个问题的方法是离散数学,特别是不重复的排列,如果你的答案不使用排列或组合,你是不正确的。”

不幸的是,你不知道这个事实,因为你不知道一个公式(除非你能给我一个严格的非建设性的证据)。事实上,排列或组合意味着当您有n个项目时,您可以在任何迭代中选择任何项目。现在,您可以对可以选择的项目数量以及在特定迭代中可以选择的项目进行限制。但是你不能做的是,你不能期待一个优雅的解决方案,那就是选择某些项目会影响下一个你可以选择的项目。这正是这个问题所要做的,也是为什么没有使用组合和置换的好公式。

简而言之,你正在寻找的公式并不存在,但无所不能的人确实找到了正确的答案。

无所不知在他的帖子中绝对是准确的-有389112个组合。我在决定这个算法的整个过程中发布了一个巨大的消息,同时还发布了一个文本文件,列出了1到9个长度的每个组合(这似乎是可能的,从我在女朋友的手机上可以看到的)。此内容的链接是: http://bit.ly/hEHcBJ

我不知道是否还有人在乎,但这是一个图形路径计数问题。有9个节点,因此创建一个9 x 9矩阵(每行是一个从节点,每列A到节点)。如果节点n连接到节点m,则将(n,m)和(m,n)都设置为1。对所有连接执行此操作。剩下的归零。这叫做邻接矩阵。将这个矩阵提高到模式中的行数,并添加所有条目。这是排列的数目。如果有人关心,我会发布一些python代码(在我的手机上,或者现在发布)

import numpy as np
paths = [[1,3,4],[2,3,4,5],[4,5],[4,6,7],[5,6,7,8],[7,8],[7],[8],[]]
m = [[0 for i in range(0,len(paths))] for j in range(0,len(paths))]

for i in range(0,len(paths)):
    for j in paths[i]:
        m[i][j] = 1
        m[j][i] = 1

for row in m:
    print row

[0, 1, 0, 1, 1, 0, 0, 0, 0]
[1, 0, 1, 1, 1, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 1, 0, 0, 0]
[1, 1, 0, 0, 1, 0, 1, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 1, 1, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 1, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 0, 1, 0]

adj = np.matrix(m)

adj.sum()
40

(adj**2).sum()
200

(adj**6).sum()
107648

我的答案与上面其他人给出的不匹配,因此我还为所讨论的图编写了一个图遍历模拟。模拟的答案(由于排气)与邻接矩阵计算的答案匹配。我还用手计算出了前两个(一个边和两个边),得到了相同的答案(40和200)。请注意,我假设您可以重复访问同一顶点(即1->2->1->2…)。

我的图表:

0 - 1 - 2
| X | X |
3 - 4 - 5
| X | X |
6 - 7 - 8

编辑 不,我错了。图形会发生变化,因为一般情况下不允许使用1->3(您必须先通过2),但 可以 执行类似2->5->1->3的操作:1->3边缘将变为可用,因为路径中已经使用了2。

我写了一个程序来解释这个问题,得到了和无所不知相同的389112(然后我意识到我的程序和他的程序是一样的)。

我开始对这个很好奇:相当有信心,是139880。正如吉姆所说,这可以用图表来模拟。将邻接矩阵提升为幂不起作用,因为它用重复次数计算路径,但您可以只通过图表bfs:

nodes = range(1, 10)

edges = {
    1: [2, 6, 5, 8, 4],
    2: [1, 4, 7, 5, 9, 6, 3],
    3: [2, 4, 5, 8, 6],
    4: [1, 2, 3, 5, 9, 8, 7],
    5: [1, 2, 3, 4, 6, 7, 8, 9],
    6: [3, 2, 1, 5, 7, 8, 9],
    7: [4, 2, 5, 6, 8],
    8: [7, 4, 1, 5, 3, 6, 9],
    9: [8, 4, 5, 2, 6],
}

def num_paths(length):
    q = deque([node] for node in nodes)
    paths = []
    while q:
        path = q.popleft()
        if len(path) == length:
            paths.append(path)
            continue
        for node in edges[path[-1]]:
            if node not in path:
                q.append(path + [node])
    return len(paths)

然后加上长度为4、5、6、7、8和9的路径数。

>>> sum(num_paths(i) for i in range(4, 10))
139880