удаление повторяющихся циклов ориентированного графа из списка в 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) Список (0, 1, 3, 4, 0) Список (0, 2, 3, 4, 0) - это уникальные пути, и общее число будет равно 3. Список (0, 1, 2, 4,0) и List (4,0,1,2,4) - один и тот же цикл, поэтому мы берем один из них.

Я пытался использовать фильтр, но не смог найти никакой логики для этого.

Answer 1

Должны работать следующие:

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 2

... красные циклы от руки к спасению.

Вот два разных цикла в тех же четырех вершинах , что показывает, что сортировка Недостаточно :

В эскизе предполагается, что все точки являются вершинами полностью связного графа (ребра опущены), и должно отображатьсячто циклы [0, 1, 2, 3, 0] и [0, 2, 1, 3, 0] не совпадают, несмотря на то, что при сортировке наборов вы получаете [0, 1, 2, 3] в обоих случаях.

Вот что может работать вместо:

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 делает:

1. tail удаляет дублирующую вершину: [2, 1, 0, 4, 2] -> [1, 0, 4, 2]
2. splitAt находит минимальную вершину и сокращает список: [1, 0, 4, 2] -> ([1], [0, 4, 2])
3. a ++ b перестраивает повернутый список: [0, 4, 2, 1]
4. :+ добавляет минимальную вершину к концу: [0, 4, 2, 1, 0]

Answer 3

1. Удалить последний элемент из списка (он избыточен)
2. Прокрутить списки, чтобы начать с наименьшего идентификатора
3. Сортировать циклы по длине, кратчайшей первой
4. Вы можете использовать лексическое соответствие сейчас (если цикл [i] содержит какой-либо цикл [0..i-1] -> отбросить его)