How many kinds of squares password

#

上礼拜和yld吃饭，聊了聊最近的业内优秀开源项目以及算法方面的东西。yld表示自己当年能够用笔一字不改的手撕KMP算法，对现在功力的退步表示遗憾。
然后闲聊之际yld掏出手机解锁，由此引申出一道算法题：九宫格密码到底有多少种？

九宫格密码

经过尝试，安卓系统的九宫格密码有这样一些限制条件，假设九宫格的布局如下：

1
2
3
1 2 3
4 5 6
7 8 9

那么：

  1. 至少使用4个点
  2. 不能重复经过同一个点
  3. 路径上的中间点不能跳过（例如 1 -> 3 -> 6 -> 9 是不合法的，因为2被跳过了）
  4. 如果中间的点之前已经用过，那么该点就可以被跳过（例如 2 -> 1 -> 3 -> 6是合法的，因为在 1 -> 3之前2已经被使用过）

首先考虑最简单的情况

首先只考虑条件1和条件2，那么这种排列组合的方式一共有A(9, 4) + A(9, 5) + A(9, 6) + A(9, 7) + A(9, 8) + A(9, 9)种。
当然，如果你就直接把这个答案写上去的话我们就没办法继续往下写了。所以我们还是用代码一个一个的数出来吧-。-

（最近在学习scala，我用scala练习一下）

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
object PasswordPermutation {

  //长度为m的排列组合
  def password_permutation_with_length(n: Int, m: Int) = {

      def helper(llist: List[List[Int]], n:Int, m: Int): List[List[Int]] = {
        if(m == 0) llist
        else {
          val pre_list = for(list <- llist ; i <- 1 to n; if(!list.contains(i))) yield
              list ++ List(i)
          helper(pre_list, n, m-1)
        }
      }

      helper(List(Nil), n, m)
    }

  //满足条件1 2 的排列组合
  def  password_permutation(n: Int) = (for(i <- (4 to n).toList)
                          yield password_permutation_with_length(n, i)).flatten

  //测试
  def main(args: Array[String]) {
    val result = password_permutation(9)
    println("count:" + result.length)
  }

}

然后加入限制条件

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
object PasswordPermutation {

  //所有规则3禁止的类别
  val forbidden:Map[Int, List[Int]] = Map(
    1 -> List(3, 7, 9),
    2 -> List(8),
    3 -> List(1, 7, 9),
    4 -> List(6),
    5 -> Nil,
    6 -> List(4),
    7 -> List(1, 3, 9),
    8 -> List(2),
    9 -> List(1, 3, 7)
  )

  //规则3与规则4的限制条件
  def is_forbidden(list: List[Int], i: Int) = {
    if(list isEmpty) false
    else forbidden(list.last).contains(i) && !list.contains((list.last + i)/2)
  }

  //长度为m的排列组合（加入限制条件3 4）
  def password_permutation_with_length(n: Int, m: Int) = {

      def helper(llist: List[List[Int]], n:Int, m: Int): List[List[Int]] = {
        if(m == 0) llist
        else {
          val pre_list = for(list <- llist ; i <- 1 to n; if(!list.contains(i) && !is_forbidden(list, i))) yield
              list ++ List(i)
          helper(pre_list, n, m-1)
        }
      }

      helper(List(Nil), n, m)
    }

  //满足条件1 2 3 4的排列组合
  def  password_permutation(n: Int) = (for(i <- (4 to n).toList)
                          yield password_permutation_with_length(n, i)).flatten

  //测试
  def main(args: Array[String]) {
    val result = password_permutation(9)
    println("count:" + result.length)
  }

}

运行得到结果:

1
count:389112

最后

原来只是这么简单一道题目啊-。- 还以为发现了不得了的东西呢-。-