Как найти одинаковые края двух путей?

Question

Путь представлен вектором, содержащим идентификатор узла. Кромка в пути имеет направление.

Указанные две дорожки, например: < 1,6,11,7,2,5 ...> и < 3, 4, 8, 2, 7,3, 1,6 ...>, здесь < 1,6> - тот же край. Иногда края чередуются, иногда нет. Лучше поставить флаг между этими краями. Например, (1,2) * (5,7,9) * (6,11,12) являются одинаковыми краями 1-> 2, 5-> 7,7-> 9, 6-> 11, 11 -> 12, но нет ребер от 2 до 5 или от 9 до 6. Поэтому поставьте символ «*» или другой символ в качестве флага.

Есть ли у кого-нибудь идеи? Я буду признателен.

Answer 1

Предполагая, что каждый узел имеет только один входящий и один исходящий фронт. Вызовите P1 первым путем длины n и P2 вторым путем длины m. Вы можете превратить P2 в хэш-карту startEdge -> endEdge (например, <3,4,5> станет [3->4, 4->5]).

Затем для каждого элемента P1, например, номер i, вы сравниваете P1(i+1) с Hashmap(key= P1(i)). Если hashmap не имеет ключа или имеет его, но с другим значением, у вас нет общего края, иначе вы это сделаете.

(Если у вас есть несколько ребер для одного узла, значения hashmap могут быть наборами Ints, и вы должны проверить, содержится ли P1(i+1) в пределах Hashmap(key=P1(i))).

Answer 2

Вот пример решения в Clojure:

(defn same-edges [& paths] 
    (->> paths 
     (map (comp set (partial partition 2 1))) 
     (apply clojure.set/intersection))) 

Таким образом, для каждого пути (map по всем paths), вы partition путь в 2-элементных подпутей (используя шаг 1, чтобы получить все пары смежные элементы), затем вычислить set всех уникальных пар, полученных из этого раздела. Затем вы найдете intersection всех этих наборов.

Пример:

(same-edges [1 6 11 7 2 5] [3 4 8 2 7 3 1 6]) 
;=> #{(1 6)} 

Другими словами, множество общих ребер между двумя дорожками, представленных векторами [1 6 11 7 2 5] и [3 4 8 2 7 3 1 6] содержит только один элемент: пара (1 6).