本文介绍了android模式锁定中可能的路径数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

android模式锁定中可能有多少条路径?

How many paths possible in android pattern lock?

我认为可以简单地通过阶乘计算公式为(9!)/ (9个长度)!

I thought it can be calculated simply by factorial, with formula (9!)/(9-length)!

示例:

对于长度9,是9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1路径。

For length 9, there are 9*8*7*6*5*4*3*2*1 paths.

对于长度8,有9 * 8 * 7 * 6 * 5 * 4 * 3 * 2条路径。

For length 8, there are 9*8*7*6*5*4*3*2 paths.

对于长度7,有9 * 8 * 7 * 6 * 5 * 4 * 3条路径。

For length 7, there are 9*8*7*6*5*4*3 paths.

等。

以下是计算此代码的代码:

Here is the code for calculating this:

def paths_of_length(number_of_staring_points, length_of_path):
    print("number_of_staring_points", number_of_staring_points, "length_of_path", length_of_path)
    different_paths = 1
    for choosing_from in range(number_of_staring_points,
                               number_of_staring_points - length_of_path,
                               -1):
        different_paths = different_paths * choosing_from

    return different_paths

def android_paths():
    """
    Returns number of different android lockscreen paths
    """
    different_paths = 0
    minimum_length = 4
    maximum_length = 9
    number_of_staring_points = 9
    for length in range(minimum_length,maximum_length + 1):
        different_paths += paths_of_length(number_of_staring_points,length)

    return different_paths

if __name__ == '__main__':
    import doctest
    doctest.testmod()

print(android_paths())

我的方法和代码正确吗?还是我计算错了?

Is my method, and the code correct? Or am I calculating it wrong?

预先感谢。

推荐答案

您的计算是错误的,因为并非每个节点都具有到另一个节点的边缘,并且某些节点只有在某些条件下才启用某些边缘。

Your calculation is wrong, because not every node has edge to another node, and some nodes have some edges only enabled by some conditions.

例如:从顶部到达左节点到右上节点,应该先访问上中间节点。

For example: To reach from top-left node to top-right node, top-middle node should be visited before.

您不能简单地通过乘以一些数字来计算它。您需要使用路径查找算法。

You can't calculate it simply by multiplying some numbers. You need to use a path finding algorithm.

好消息,我写过一个。

这是一个实用程序类:

import java.util.ArrayList;
import java.util.HashMap;

public class Node
{

    private String name;

    private HashMap<Node, Node> conditionalNeigbors = new HashMap<>();

    private ArrayList<Node> neigbors = new ArrayList<>();
    private boolean visited = false;

    public Node(String name)
    {
        this.name = name;
    }

    void addNeigbor(Node n)
    {
        this.neigbors.add(n);
    }

    void addConditionalNeigbor(Node condition, Node n)
    {
        conditionalNeigbors.put(condition, n);
    }

    ArrayList<Node> getNeigbors(ArrayList<Node> path)
    {

        ArrayList<Node> toReturn = new ArrayList<>();
        ArrayList<Node> conditionals = new ArrayList<>();
        for (int i = 0; i < path.size(); i++)
        {
            if(conditionalNeigbors.containsKey(path.get(i)))
            {
                conditionals.add(conditionalNeigbors.get(path.get(i)));
            }
        }

        toReturn.addAll(neigbors);
        toReturn.addAll(conditionals);

        return toReturn;
    }

    void setVisited(boolean b)
    {
        visited = b;
    }

    boolean getVisited()
    {
        return visited;
    }

    public String getName()
    {
        return name;
    }


}

类:

import java.util.ArrayList;

public class Pathfinder
{

    static boolean debug = false;

    /**
     * A B C
     *
     * D E F
     *
     * G H J
     */
    public static void main(String[] args)
    {

        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        Node h = new Node("H");
        Node j = new Node("J");

        a.addNeigbor(b);
        a.addNeigbor(d);
        a.addNeigbor(e);
        a.addNeigbor(h);
        a.addNeigbor(f);
        a.addConditionalNeigbor(b, c);
        a.addConditionalNeigbor(d, g);
        a.addConditionalNeigbor(e, j);

        b.addNeigbor(a);
        b.addNeigbor(d);
        b.addNeigbor(e);
        b.addNeigbor(f);
        b.addNeigbor(c);
        b.addNeigbor(g);
        b.addNeigbor(j);
        b.addConditionalNeigbor(e, h);

        c.addNeigbor(b);
        c.addNeigbor(e);
        c.addNeigbor(f);
        c.addNeigbor(d);
        c.addNeigbor(h);
        c.addConditionalNeigbor(b, a);
        c.addConditionalNeigbor(e, g);
        c.addConditionalNeigbor(f, j);

        d.addNeigbor(a);
        d.addNeigbor(b);
        d.addNeigbor(e);
        d.addNeigbor(g);
        d.addNeigbor(h);
        d.addNeigbor(c);
        d.addNeigbor(j);
        d.addConditionalNeigbor(e, f);

        e.addNeigbor(a);
        e.addNeigbor(b);
        e.addNeigbor(c);
        e.addNeigbor(d);
        e.addNeigbor(f);
        e.addNeigbor(g);
        e.addNeigbor(h);
        e.addNeigbor(j);

        f.addNeigbor(c);
        f.addNeigbor(b);
        f.addNeigbor(e);
        f.addNeigbor(h);
        f.addNeigbor(j);
        f.addNeigbor(a);
        f.addNeigbor(g);
        f.addConditionalNeigbor(e, d);

        g.addNeigbor(d);
        g.addNeigbor(e);
        g.addNeigbor(h);
        g.addNeigbor(b);
        g.addNeigbor(f);
        g.addConditionalNeigbor(d, a);
        g.addConditionalNeigbor(e, c);
        g.addConditionalNeigbor(h, j);

        h.addNeigbor(d);
        h.addNeigbor(e);
        h.addNeigbor(f);
        h.addNeigbor(g);
        h.addNeigbor(j);
        h.addNeigbor(a);
        h.addNeigbor(c);
        h.addConditionalNeigbor(e, b);

        j.addNeigbor(f);
        j.addNeigbor(e);
        j.addNeigbor(h);
        j.addNeigbor(d);
        j.addNeigbor(b);
        j.addConditionalNeigbor(h, g);
        j.addConditionalNeigbor(f, c);
        j.addConditionalNeigbor(e, a);

        ArrayList<Node> graph = new ArrayList<>();
        graph.add(a);
        graph.add(b);
        graph.add(c);
        graph.add(d);
        graph.add(e);
        graph.add(f);
        graph.add(g);
        graph.add(h);
        graph.add(j);

        int sum = 0;

        System.out.println(countPaths(b, 3, new ArrayList<>()));

        for (int k = 1; k < 10; k++)
        {
            for (int i = 0; i < graph.size(); i++)
            {
                sum += countPaths(graph.get(i), k, new ArrayList<>());
            }

            System.out.println("Number of all paths with length of " + k + ": " + sum);
            sum = 0;
        }
    }

    /*
        Finds number of all possible paths of given length, starting from given node
     */
    static int countPaths(Node start, int length, ArrayList<Node> path)
    {

        start.setVisited(true);
        path.add(start);

        ArrayList<Node> neigbors = start.getNeigbors(path);
        int neigborCount = neigbors.size();
        ArrayList<Node> unvisitedNeighbors = new ArrayList<>();

        for (int i = 0; i < neigborCount; i++)
        {
            Node temp = neigbors.get(i);

            if (temp.getVisited() == false)
            {
                unvisitedNeighbors.add(temp);
            }
        }

        int unvisitedNeighborCount = unvisitedNeighbors.size();

        if (length == 1) // Base case, no more moves, a path found, return 1
        {
            if (debug)
            {
                for (int i = 0; i < path.size(); i++)
                {
                    System.out.print(path.get(i).getName());
                }
                System.out.println("");
            }

            start.setVisited(false); // Backtrack
            path.remove(path.size() - 1);

            return 1;
        } else // There are still moves
        {
            int sum = 0;
            for (int i = 0; i < unvisitedNeighborCount; i++)
            {
                sum += countPaths(unvisitedNeighbors.get(i), length - 1, path);
            }

            start.setVisited(false); // Backtrack
            path.remove(path.size() - 1);

            return sum;
        }
    }

}

不,您不必运行此程序。我为您计算了所有条件:

No, you don't have to run this. I have calculated all for you:

Number of all paths with length of 1: 9
Number of all paths with length of 2: 56
Number of all paths with length of 3: 320
Number of all paths with length of 4: 1624
Number of all paths with length of 5: 7152
Number of all paths with length of 6: 26016
Number of all paths with length of 7: 72912
Number of all paths with length of 8: 140704
Number of all paths with length of 9: 140704






说明



我把问题变成了无向循环图搜索问题。


Explanation

I turned the problem into a undirected cyclic graph search problem.

A  B  C
D  E  F
G  H  J




  • 点表示为 Node s

  • 法律移动表示为 Edge s

  • 每个 Node 访问的属性

  • 有两种类型的边:始终可用和有条件的。有条件移动的一个示例:仅当访问B时,才可能使用A-C。

  • 从给定节点开始搜索给定路径长度(空路径)。在每次迭代中,算法都会获取可能的边沿(考虑条件边沿),然后从下一个节点开始递归调用子搜索。

    • Points are represented as Nodes
    • Legal moves are represented as Edges
    • Every Node has a visited property
    • There are two types of edges: Always available ones, and conditional ones. An example to conditional move: A-C possible only when B is visited.
    • Search starts from a given node for given length of paths, with empty path. In each iteration, algorithm obtains possible edges(taking account of conditional edges) and recursively calls a sub-search starting from next nodes.
    • 示例

      这是示例呼叫跟踪,用于搜索从节点B开始的长度为3的路径。

      This is an example call trace, for searching paths length of 3, starting from node B.

      _\ countPaths(B, 3, null)
         _\ countPaths(A, 2, B)
            _\ countPaths(C, 1, BA)
            _\ countPaths(D, 1, BA)
            _\ countPaths(E, 1, BA)
            _\ countPaths(F, 1, BA)
            _\ countPaths(H, 1, BA)
         _\ countPaths(C, 2, B)
            _\ countPaths(A, 1, BC)
            _\ countPaths(D, 1, BC)
            _\ countPaths(H, 1, BC)
            _\ countPaths(E, 1, BC)
            _\ countPaths(F, 1, BC)
         _\ countPaths(D, 2, B)
            _\ countPaths(A, 1, BD)
            _\ countPaths(E, 1, BD)
            _\ countPaths(G, 1, BD)
            _\ countPaths(H, 1, BD)
            _\ countPaths(C, 1, BD)
            _\ countPaths(J, 1, BD)
         _\ countPaths(E, 2, B)
            _\ countPaths(A, 1, BE)
            _\ countPaths(C, 1, BE)
            _\ countPaths(D, 1, BE)
            _\ countPaths(F, 1, BE)
            _\ countPaths(G, 1, BE)
            _\ countPaths(H, 1, BE)
            _\ countPaths(J, 1, BE)
         _\ countPaths(F, 2, B)
            _\ countPaths(C, 1, BF)
            _\ countPaths(E, 1, BF)
            _\ countPaths(H, 1, BF)
            _\ countPaths(J, 1, BF)
            _\ countPaths(A, 1, BF)
            _\ countPaths(G, 1, BF)
         _\ countPaths(G, 2, B)
            _\ countPaths(D, 1, BG)
            _\ countPaths(E, 1, BG)
            _\ countPaths(H, 1, BG)
            _\ countPaths(F, 1, BG)
         _\ countPaths(J, 2, B)
            _\ countPaths(F, 1, BJ)
            _\ countPaths(E, 1, BJ)
            _\ countPaths(H, 1, BJ)
            _\ countPaths(D, 1, BJ)
      

      因此,它只是将问题分为较小的子类别,问题,直到遇到长度为1的问题,其中解为1(基本情况)。

      So it simply divides problems into smaller sub-problems, until it gets a problem with length of 1 where solution is 1(base case).

      因此,找到了给定节点的所有路径后,我们需要做的所有事情是枚举所有9个节点的操作,这是通过 main()方法中的简单for循环完成的,只需调用 countPaths()方法。

      So after finding all path from a given node, all we need to do is to enumerate this operation for all 9 nodes, which is done by a simple for loop in main() method, simply by calling countPaths() methods.

      这篇关于android模式锁定中可能的路径数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-03 10:24