Должен ли я использовать `assoc` в этой функции для переопределения аргумента функции?

Я реализую алгоритм Брона-Кербоша в Clojure для проекта класса и имею некоторые проблемы. Проблема заключается в последних строках алгоритма

BronKerbosch1(R, P, X):
 if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v} ;This line
       X := X ⋃ {v} ;This line

Я знаю, что в Clojure нет смысла «установить x = что-то». Но знайте, что есть функция assoc, которая, я думаю, похожа. Я хотел бы знать, подходит ли assoc для завершения моей реализации.

В моей реализации графики представлены так

[#{1 3 2} #{0 3 2} #{0 1 3} #{0 1 2}]

Где 0-й узел представлен как первый набор в векторе, а значения в наборе представляют ребра к другим узлам. Таким образом, приведенное выше представляет собой полный граф с 4 узлами (все узлы связаны со всеми другими узлами).

Пока моя реализация алгоритма

(defn neighV [graph, v]
  (let [ret-list (for [i (range (count graph)) :when (contains? (graph i) v)] i)]
    ret-list))

(defn Bron-Kerbosch [r, p, x, graph, cliques]
  (cond (and (empty? p) (empty? x)) (conj cliques r)
        :else
        (for [i (range (count p))]
          (conj cliques (Bron-Kerbosch (conj r i) (disj p (neighV graph i) (disj x (neighV graph i)) graph cliques)))
          )))

Так что сейчас я застрял, изменяя p и x в соответствии с алгоритмом. Я думаю, что я могу использовать assoc для этого, но я думаю, что это применимо только к картам. Можно ли будет использовать, может кто посоветует другую функцию?


algorithm clojure
person KDecker    schedule 27.03.2015    source источник
comment
Я немного смущен вашим вопросом. assoc на самом деле не map a = something, он возвращает новую карту с измененной или добавленной парой K/V. Итак, если бы существовало assoc для наборов, выполнение (assoc someSet 2) не изменило бы какой-то набор, у вас был бы просто новый набор.   -  person t_scho    schedule 28.03.2015
comment
Ааа, понятно.. Наверное, я неправильно думал об этом. Я предполагаю, что тогда мне нужен способ переопределить переменную на месте.   -  person KDecker    schedule 28.03.2015
comment
KDecker: это доказуемая основа функционального программирования, которую вам никогда не нужно обновлять на месте. for необходимо изменить на reduce или loop, чтобы каждый шаг видел обновленное значение.   -  person noisesmith    schedule 28.03.2015

Ответы (2)


arrow_upward
1
arrow_downward

assoc не изменяет свой аргумент. Как и все другие базовые операции с коллекциями в Clojure, она возвращает новую неизменяемую коллекцию.

Чтобы выполнять обновления «на месте», вам нужно будет отказаться от использования базовых типов данных Clojure и использовать собственные типы данных Java, такие как java.util.HashSet.

Другой (и предпочтительный) вариант — реорганизовать алгоритм таким образом, чтобы все обновления передавались следующей итерации или рекурсии кода.

Вот первоначальная попытка приспособить ваш код к этому стилю, с оговоркой, что может потребоваться внутренняя модификация из рекурсивного вызова:

(defn Bron-Kerbosch
  [r p x graph cliques]
  (if (every? empty? [p x])
    (conj cliques r)
    (reduce (fn [[cliques p x] v]
              (let [neigh (neighV graph v)]
                [(conj cliques
                       ;; do we need to propagate updates to p and x
                       ;; from this call back up to this scope?
                       (Bron-Kerbosch (conj r v)
                                      (disj p neigh)
                                      (disj x neigh)
                                      graph
                                      cliques))
                 ;; here we pass on the new values for p and x
                 (disj p v)
                 (conj x v)]))
            [cliques p x]
            (range (count p)))))
person noisesmith    schedule 27.03.2015
comment
Если вы ожидаете, что рекурсивный вызов Bron-Kerbosch изменит родительское значение p и x, Брон-Кербошу потребуется вспомогательная функция, чтобы она могла либо возвращать cliques вместе с новыми значениями p и x вызывающей стороне, либо просто возвращать cliques для случая верхнего уровня. - person noisesmith; 28.03.2015

arrow_upward
0
arrow_downward

Я думаю, учитывая ваш комментарий, вам будет лучше использовать loop и recur. На самом деле это не сильно отличается от того, что у вас есть сейчас, но это устранит рекурсивный вызов функции.

person t_scho    schedule 27.03.2015