【算法】最大前驱路径代码示例

一. 问题描述

在网络环境下，用户对链接的访问可能出现前进或者后退的情况，不会一层不变按照固定好的站点结构走下去， 具体的说在一个用户访问的session中，用户有目的的完成一件任务需要经过1,2,3,4步，但是在实际过程中可能 出现过重复比如进行1,2,3,2,3,4的操作来进行，目的就是还原用户的真实的路径信息，为以后模式的发现提供更加清洁的数据。

二. 解决思路：

我们只关注向前的访问，当面临后退的访问的时候，其相应的向前的访问就停止了

三. 举例介绍：

一个用户的访问session有如下的路径{A,B,C,D,C,B,E,G,H,G,W,A,O,U,O,V},这里我们需要得到其最大的向前的访问路径为{ABCD,ABEGH,ABEGW,AOV,AOU}, 我们把访问路径以属的形式进行展开，就可以清楚的看到用户的访问路径,形象化的图示如下：

image.png

步骤

image.png

object Test {
  def main(args: Array[String]): Unit = {

    val list = List("A", "B", "C", "D", "C", "B", "E", "G", "H", "G", "W", "A", "O", "U", "O", "V")
    //    val list = List("A", "B", "C", "D", "C", "B", "E", "G", "H", "G", "W", "A", "O", "U", "O" )
    val y = new util.ArrayList[String]()
    var forward = true
    for (i <- 0 to list.size - 1) {
      val cur = list(i)
      if (y.size() == 0) {
        y.add(cur)
      } else {
        val index = y.indexOf(cur)
        if (index > -1) {
          if (forward == true) {
            print(y)
            forward = false
          }
          remove(y, index)
        } else if (i < list.size - 1) {
          y.add(cur)
          forward = true
        } else {
          y.add(cur)
          print(y)
        }
      }

    }

  }

  def print(list: java.util.ArrayList[String]): Unit = {
    var record = ""
    for (i <- 0 to list.size() - 1) {
      record = record + "_" + list.get(i)
    }
    println(record)
  }

  def remove(list: java.util.ArrayList[String], index: Int): Unit = {
    var cur = list.size() - 1
    while (cur > index) {
      list.remove(cur)
      cur = cur - 1
    }
  }
}

参考文献

http://pdfs.semanticscholar.org/14b8/1642caa8b3b664a553201d9daab0306ce96b.pdf