从 Scala 列表中删除有向图的重复循环

Question

我收集了如下所示的列表。

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)

这些列表是循环长度为 4 的有向图中的各个循环。我想从给定列表中过滤掉中间没有任何更小路径的唯一路径的数量。例如 - List(4,0,1,2,4) 和 List(0,1,2,4,0) 形成相同的循环。另一个例子 - List(2,3,2,3,2) 仅迭代 2 和 3 并且不形成循环长度 4.

从这个集合我们可以说 List(0, 1, 2, 4, 0) List(0, 1, 3, 4, 0) List(0, 2, 3, 4, 0) 是唯一路径和总数为 3。 List(0, 1, 2, 4, 0) 和 List(4,0,1,2,4) 是同一个循环，所以我们取其中一个。

我尝试使用过滤器，但无法找到执行此操作的任何逻辑。

Answer 1

从列表中删除最后一个元素（它是多余的）
从最小的 ID 开始滚动列表
按长度最短的循环排序
您现在可以使用词法匹配（如果 loop[i] 包含任何 loop[0..i-1] -> 丢弃它）

Answer 2

以下应该有效：

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}

Answer 3

...手绘红色循环来拯救。

这里有两个不同圈在相同的四个顶点，说明排序不够:

草图假定所有点都是完全连接图的顶点（省略边），并且应该表明循环 [0, 1, 2, 3, 0] 和 [0, 2, 1, 3, 0] 不相同，尽管事实上，如果你对集合进行排序，你在两种情况下都会获得 [0, 1, 2, 3]。

以下可能有效：

通过过滤掉所有不包含四个不同元素的路径，丢弃所有多次通过同一顶点的路径。
将路径表示旋转为规范形式（例如，从具有最小位置的顶点开始）。
计算规范表示集，仅保留唯一路径。

实现可能如下所示：

def canonicalize(cycle: List[Int]) = {
  val t = cycle.tail
  val (b, a) = t.splitAt(t.zipWithIndex.minBy(_._1)._2)
  val ab = (a ++ b)
  ab :+ (ab.head)
}

val cycles = 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)
)

val unique = cycles.filter(_.toSet.size == 4).map(canonicalize).toSet

unique foreach println

输出：

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

canonicalize 功能的逐行示例：

tail 删除重复顶点：[2, 1, 0, 4, 2] -> [1, 0, 4, 2]
splitAt找到最小顶点并切割列表：[1, 0, 4, 2] -> ([1], [0, 4, 2])
a ++ b 重建旋转列表：[0, 4, 2, 1]
:+ 将最小顶点附加到末尾：[0, 4, 2, 1, 0]

从 Scala 列表中删除有向图的重复循环

removing duplicate cycles of directed graph from a list in scala

scala

graph

cycle