Java计算手机九宫格锁屏图案连接9个点的方案总数
(一)问题
九宫格图案解锁连接9个点共有多少种方案?
(二)初步思考
可以把问题抽象为求满足一定条件的1-9的排列数(类似于“八皇后问题”),例如123456789和987654321都是合法的(按照从上到下、从左到右、从1到9编号),解决此类问题一般都用递归方法,因为问题规模较大,且没有明确的计算方法
(三)深度思考
不难想出下面的简单思路:
1.先穷举,再排除不合法结果(过滤穷举的结果)
大略估计一下复杂度,A99=362880(计算机应该可以接受),方案总数不超过A99,也就是说穷举的结果是A99,再滤去不合法的结果即可,理论上此方法可行
2.按条件穷举(在穷举的过程中排除不合法结果)
1>正常思维
---a.选择起点位置(i,j)
---b.在起点周围寻找合法终点,规则如下:(共有12个方向)
------1.上(i - 1, j)--5.左上斜(i - 1, j - 1)---9.左上长斜(i - 2, j - 1)
------2.下(i + 1, j) -6.左下斜(i + 1, j - 1) -10.左下长斜(i + 2, j - 1)
------3.左(i, j - 1)--7.右上斜(i - 1, j + 1)--11.右上长斜(i - 2, j + 1)
------4.右(i, j + 1) -8.右下斜(i + 1, j + 1)-12.右下长斜(i + 2, j + 1)
---c.记录路径(起点 + 终点)
---d.判满,若路径长度小于9执行e步骤,否则执行f步骤
---e.终点变起点,返回a步骤
---f.输出结果(路径)
2>逆向思维
---a.排除(1.排除已选择的点2.排除从起点不能到达的点)得到临时剩余点集
---b.在临时剩余点集中选择下一个点
---c.判满,路径长度小于9,执行d步骤,否则执行e步骤
---d.执行a步骤
---e.输出结果(路径)
P.S.正常思维比较容易理解,逆向思维更容易实现
(四)编码
[最初想用方案2的逆向思维方案来实现,结果失败了,原因是递归内嵌循环,程序执行轨迹难以捉摸...头疼良久之后放弃了,改用方案1,简单粗暴]
[核心代码类]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class ScreenLock { //将NUM设置为待排列数组的长度即实现全排列 private
int NUM = 0 ; private
int count = 0 ; private
String[] strSource; String string = null ; private
static String[] wrongPos = { //各点对应的不能到达的位置 "379" , "8" , "179" , "6" , "#" , "4" , "139" , "2" , "137" }; public
ScreenLock(String[] strSource) { //strSource格式为以逗号分隔的数字串,如1,2,3,4 //初始化 this .strSource = strSource; this .NUM = strSource.length; } public
int getCount() { sort(Arrays.asList(strSource), new
ArrayList()); return
count; } private
void sort(List datas, List target) { if
(target.size() == NUM) { StringBuilder sb = new
StringBuilder(); for
(Object obj : target) sb.append(obj); String ans = sb.toString(); if (isValid(ans)) count++; return ; } for
( int i = 0 ; i < datas.size(); i++) { List newDatas = new
ArrayList(datas); List newTarget = new
ArrayList(target); newTarget.add(newDatas.get(i)); newDatas.remove(i); sort(newDatas, newTarget); } } private
boolean isValid(String ans) { //判断ans是否合法 for ( int
i = 0 ;i < ans.length() - 1 ;i++) { //获取当前位置的字符的值 int
currPos = Integer.parseInt(ans.charAt(i) + "" ); //获取路径子串 String path = ans.substring( 0 , i + 1 ); //获取错误值 String wrrPos = wrongPos[currPos - 1 ]; //获取可变错误值 if (currPos != 5 ) //5不可能变 { for ( int
j = 0 ;j < wrrPos.length();j++) { //获取中间值 String wrong = wrrPos.charAt(j) + "" ; int
mid = (currPos + Integer.parseInt(wrong)) / 2 ; //若中间值已被连接,则错误终点可用 if (path.contains(mid + "" )) wrrPos = wrrPos.replace(wrong, "#" ); //若下一位是错误值则ans不合法 if (wrrPos.contains(ans.charAt(i + 1 ) + "" )) return
false ; } } } return
true ; } } |
特别说明:上面代码中用到的全排列算法来自http://blog.csdn.net/sunyujia/article/details/4124011 (尊重前辈的劳动成果)
[测试类]
1
2
3
4
5
6
7
8
9
10
11
12
13 |
public class CountLockPlans { public
static void main(String[] args) { //计算手机九宫格锁屏图案连接9个点的方案总数 String s = "1,2,3,4,5,6,7,8,9" ; String[] str = s.split( "," ); ScreenLock lock = new
ScreenLock(str); int
num = lock.getCount(); System.out.println( "连接9个点共有 "
+ num + " 种方案" ); } } |
(五)运行结果
连接9个点共有 62632 种方案【此结果是错的,详情见最下方第(十)点】
(六)程序正确性检验
1.能否生成1-9的全排列?
注释掉无关代码,直接输出所有全排列,同时计数,结果无误(全部输出需要17秒左右)
2.isValid()方法是否能够正确判断方案的合法性?
单独调用isValid()传入各种参数测试,结果无误
3.算法逻辑是否无误?
求排列的同时过滤不合法解,逻辑无误
[综上,理论上输出的结果是正确的]
(七)答案正确性确认
上网找找有没有人算出结果,滤去所有看起来不靠谱的答案,选定果壳网答案(据说用了Mathematica,乍看高上大)
文章中的解决思路也是:合法方案数 = 全排列总数 - 不合法方案数
原文链接:http://www.guokr.com/article/49408/
仔细看过文章后发现原文的结论可能是错的(虽然不知道其具体算法)
1.从原文的贴图可以看到先求出了方案总数985 824(这个我们不必关心,只需要关注连接9个点的计算结果就好)
2.原文贴图记下不能直接连的点对(和我们的wrongPos数组作用类似,用来排除)
3.接着往下看是:根据上一步的点对生成所有不合法方案(仍然不知道具体是怎么算的,但是这里肯定存在漏洞)
原作者的思路应该是按照相邻点来判断生成不合法方案(例如:假设第一位是1那么如果第二位选择3,则以13开头的所有方案全部PASS掉)
不难发现这样一个BUG:第一位选择2,第二位选择1,那么第三位能不能选择3呢?
实际情况是Yes,但如果按照上面假设的判断方法则是No,因为(1,3)属于不合法点对!
这就又出现新问题了,因为我们发现所谓的不合法点对好像是一个动态的集合,如果中间点被选了,那么非法点对就变成合法的了(例如2被选了之后1可以和3连接,3和1也可以连接)
我们的算法会不会存在这个问题呢?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
private
boolean isValid(String ans) { //判断ans是否合法 for ( int
i = 0 ;i < ans.length() - 1 ;i++) { //获取当前位置的字符的值 int
currPos = Integer.parseInt(ans.charAt(i) + "" ); //获取路径子串 String path = ans.substring( 0 , i + 1 ); //获取错误值 String wrrPos = wrongPos[currPos - 1 ]; //获取可变错误值 if (currPos != 5 ) //5不可能变 { for ( int
j = 0 ;j < wrrPos.length();j++) { //获取中间值 String wrong = wrrPos.charAt(j) + "" ; int
mid = (currPos + Integer.parseInt(wrong)) / 2 ; //若中间值已被连接,则错误终点可用 if (path.contains(mid + "" )) wrrPos = wrrPos.replace(wrong, "#" ); //若下一位是错误值则ans不合法 if (wrrPos.contains(ans.charAt(i + 1 ) + "" )) return
false ; } } } return
true ; } |
从上面的代码不难看出我们的算法已经考虑到了这样的情况(动态修正wrrPos)
(八)思考延伸
按照这样的方法,我们不难算出一共有多少种方案(从四个点到九个点),在此作简单分析:
1>9个点和8个点的数目应该相等(前8位数都定了,最后一位也就不能变了)
2>9个点和7个点的数目应该是2倍关系(前7位数定了,后两位只有两种排列方式,如果去掉后2位则前7位数有一半重复了)
...
设总方案数为 num,连接 i 个点的方案总数为 n( i ),例如n( 9 ) = 62632
则:1式:num = n( 4 ) + n( 5 ) + n( 6 ) + n( 7 ) + n( 8 ) + n( 9 )
2式:n( 8 ) = n( 9 ), n( 7 ) = n( 9 ) / 2, n( 6 ) = n( 9 ) / 6, n( 5 ) = n( 9 ) / 24, n( 4 ) = n( 9 ) / 120 [规律:n( i ) = n( 9 ) / A(9 - i)(9 - i)]
把2式带入1式即可求得方案总数,在此不再赘述
(九)总结
探索过程中虽然走了很多弯路,但也有不少收获,例如动态不合法判断的BUG是在尝试方案2时发现的,虽然方案2失败了,但避免了在方案1中出现类似的问题
只要思路明晰,敢于尝试,绝对没有plain try
(十)BUG修正
文中对果壳网算法提出的质疑是错误的,原文结果是对的
经过验证,本文算法存在BUG,信息如下:
当前路径是 12345687
错误原因是下一位 9被错误值#39包含
错误串为 123456879
BUG分析:出现这个BUG的原因是对自己的算法太过自信,设计算法的时候过分考虑了算法复杂度,省掉了一个不能省的循环(应该先动态修改wrrPos再对结果进行判断,原算法把二者放在一个循环里了)
现对isValid方法修改如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
private
static boolean isValid(String ans) { //判断ans是否合法 for ( int
i = 0 ;i < ans.length() - 1 ;i++) { //获取当前位置的字符的值 int
currPos = Integer.parseInt(ans.charAt(i) + "" ); //获取路径子串 String path = ans.substring( 0 , i + 1 ); //获取错误值 String wrrPos = wrongPos[currPos - 1 ]; //获取可变错误值 if (currPos != 5 ) //5不可能变 { for ( int
j = 0 ;j < wrrPos.length();j++) { //获取中间值 String wrong = wrrPos.charAt(j) + "" ; int
mid = (currPos + Integer.parseInt(wrong)) / 2 ; //若中间值已被连接,则错误终点可用 if (path.contains(mid + "" )) wrrPos = wrrPos.replace(wrong, "#" ); } //若下一位是错误值则ans不合法 if (wrrPos.contains(ans.charAt(i + 1 ) + "" )) return
false ; } } return
true ; } |
[与原算法唯一的区别是把if判断语句从循环里拿出来了,当时想法是为了节省一个循环...结果,哎...]
修正后运行结果:
连接9个点共有 140704 种方案
结论:果壳网的结论是正确的!之前对其内部算法的猜测可能有误,实属抱歉。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。