removing duplicate cycles of directed graph from a list in scala

Question

I have collection of lists shown below.

List(4, 0, 1, 2, 4)
List(4, 0, 1, 3, 4)
List(4, 0, 2, 3, 4)
List(4, 3, 2, 3, 4)
List(4, 3, 4, 3, 4)
List(0, 1, 2, 4, 0)
List(0, 1, 3, 4, 0)
List(0, 2, 3, 4, 0)
List(1, 2, 4, 0, 1)
List(1, 3, 4, 0, 1)
List(3, 4, 0, 1, 3)
List(3, 4, 0, 2, 3)
List(3, 2, 3, 2, 3)
List(3, 4, 3, 2, 3)
List(3, 2, 3, 4, 3)
List(3, 4, 3, 4, 3)
List(2, 3, 4, 0, 2)
List(2, 4, 0, 1, 2)
List(2, 3, 2, 3, 2)
List(2, 3, 4, 3, 2)

These lists are the individual cycles in a directed graph with cycle length of 4. I want to filter out the number of unique path from the given lists which does not have any smaller path in between. For example - List(4,0,1,2,4) and List(0,1,2,4,0) forms the same cycle. Another example - List(2,3,2,3,2) iterates over 2 and 3 only and does not form the cycle length 4.

From this collection we can say that List(0, 1, 2, 4, 0) List(0, 1, 3, 4, 0) List(0, 2, 3, 4, 0) are the unique paths and total number would be 3. List(0, 1, 2, 4, 0) and List(4,0,1,2,4) is the same cycle so we take one of them.

I tried to use filter but unable to find any logic to do this.

Answer 1

Following should work:

val input = List(List(4, 0, 1, 2, 4),List(4, 0, 1, 3, 4) ,List(4, 0, 2, 3, 4) ,List(4, 3, 2, 3, 4) ,List(4, 3, 4, 3, 4) ,
    List(0, 1, 2, 4, 0) ,List(0, 1, 3, 4, 0) ,List(0, 2, 3, 4, 0) ,List(1, 2, 4, 0, 1) ,List(1, 3, 4, 0, 1) ,List(3, 4, 0, 1, 3) ,
    List(3, 4, 0, 2, 3) ,List(3, 2, 3, 2, 3) ,List(3, 4, 3, 2, 3) ,List(3, 2, 3, 4, 3) ,List(3, 4, 3, 4, 3) ,
    List(2, 3, 4, 0, 2) ,List(2, 4, 0, 1, 2) ,List(2, 3, 2, 3, 2), List(2, 3, 4, 3, 2))

  var uniquePaths: mutable.Set[List[Int]] = collection.mutable.Set[List[Int]]()
  var indexes: ListBuffer[Int] = mutable.ListBuffer[Int]()

  input.zipWithIndex.foreach{x =>
    val (list, index) = (x._1, x._2)
      if(list.head==list.last) {
        val list1 = rotateArray(list.tail)
        if (list1.toSet.size == 4) {
          if(!uniquePaths.contains(list1))
            indexes.append(index)
          uniquePaths.add(list1)
        }
      }
  }

  indexes foreach{x => println(input(x))}

  def rotateArray(xs: List[Int]): List[Int] =
    xs.splitAt(xs.indexOf(xs.min)) match {case (x, y) => List(y, x).flatten}