问题描述
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
- 点表示为
Nodes - 法律移动表示为
Edges - 每个
Node的访问的属性 - 有两种类型的边：始终可用和有条件的。有条件移动的一个示例：仅当访问B时，才可能使用A-C。
- 从给定节点开始搜索给定路径长度（空路径）。在每次迭代中，算法都会获取可能的边沿（考虑条件边沿），然后从下一个节点开始递归调用子搜索。
- Points are represented as
Nodes - Legal moves are represented as
Edges - Every
Nodehas avisitedproperty - 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模式锁定中可能的路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！