Android的点密码系统的熵是多少？

Question

机器人点登录系统有多少种排列可能？我知道这个问题的解决方案在于离散数学,特别是没有重复的排列,如果你的答案没有使用排列或组合你是不正确的.

密码的长度在4到9个点之间,但总共有9个点可以进行置换.所以我的初始等式是:

9P4+9P5+9P6+9P7+9P8+9P9

但是,我知道这个等式是不完整的,因为它没有考虑所有的规则.每个点都是不同的,因为它是位置所以如果你为每个点分配一个数字,如下所示:

123
456
789

密码"1397"是不可能的,如果您尝试使用此密码,您实际上已输入"1236987",因为中间的数字是自动选择的.需要创建另一个等式来解释这些限制,然后从上面的nPr等式中减去.

此链接有一个很棒的视频,有人使用Android登录.它还详细介绍了规则.该页面上的数学是完全错误的,他甚至不接近真正的解决方案.

Answer 1

这只是部分答案.唯一相关的起始点是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 - > 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