Haruskah/dapatkah saya menggunakan `assoc` dalam fungsi ini untuk mendefinisikan ulang argumen fungsi?

Saya menerapkan algoritma Bron-Kerbosch di Clojure untuk proyek kelas dan mengalami beberapa masalah. Masalahnya terletak pada baris terakhir algoritma

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

Saya tahu di Clojure tidak ada arti "set x = sesuatu". Tapi tahukah Anda ada fungsi assoc yang menurut saya serupa. Saya ingin tahu apakah assoc sesuai untuk menyelesaikan implementasi saya.

Dalam implementasi saya, grafik direpresentasikan seperti itu

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

Dimana node ke-0 direpresentasikan sebagai himpunan pertama dalam vektor, dan nilai dalam himpunan tersebut mewakili tepi ke node lainnya. Sehingga di atas mewakili grafik dengan 4 node yang lengkap (semua node terhubung ke semua node lainnya).

Sejauh ini implementasi algoritma saya adalah

(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)))
          )))

Jadi saat ini saya terjebak dalam mengubah p dan x sesuai algoritma. Saya rasa saya dapat menggunakan assoc untuk melakukan ini tetapi menurut saya ini hanya berlaku untuk peta. Apakah mungkin untuk digunakan, bisakah seseorang merekomendasikan fungsi lain?


algorithm clojure
person KDecker    schedule 27.03.2015    source sumber
comment
Saya agak bingung dengan pertanyaan Anda. assoc sebenarnya bukan map a = something, ia mengembalikan peta baru dengan menyertakan pasangan K/V yang diubah atau ditambahkan. Jadi jika memang ada assoc untuk set, melakukan (assoc someSet 2) tidak akan mengubah someSet, Anda hanya akan memiliki set baru.   -  person t_scho    schedule 28.03.2015
comment
Ahh, begitu.. Sepertinya aku salah memikirkannya. Saya kira yang saya perlukan adalah cara untuk mendefinisikan ulang variabel yang ada.   -  person KDecker    schedule 28.03.2015
comment
KDecker: ini adalah landasan pemrograman fungsional yang dapat dibuktikan sehingga Anda tidak perlu memperbarui apa pun yang ada. for perlu diubah menjadi reduce atau loop sehingga setiap langkah melihat nilai yang diperbarui.   -  person noisesmith    schedule 28.03.2015

Jawaban (2)


arrow_upward
1
arrow_downward

assoc tidak mengubah argumennya. Seperti semua operasi pengumpulan dasar lainnya di Clojure, operasi ini mengembalikan koleksi baru yang tidak dapat diubah.

Untuk melakukan pembaruan "di tempat", Anda harus berhenti menggunakan tipe data dasar Clojure, dan menggunakan tipe Java asli seperti java.util.HashSet.

Opsi lainnya (dan lebih disukai) adalah memfaktorkan ulang algoritme Anda sehingga semua pembaruan diteruskan ke iterasi atau rekursi kode berikutnya.

Berikut adalah upaya awal untuk menyesuaikan kode Anda dengan gaya ini, dengan peringatan bahwa modifikasi bagian dalam mungkin perlu diambil dari panggilan rekursif:

(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
Jika Anda mengharapkan panggilan rekursif ke Bron-Kerbosch untuk mengubah nilai induk dari p dan x, Bron-Kerbosch akan memerlukan fungsi pembantu sehingga dapat mengembalikan cliques bersama dengan nilai baru p dan x ke pemanggil, atau hanya mengembalikan cliques untuk kasus tingkat atas. - person noisesmith; 28.03.2015

arrow_upward
0
arrow_downward

Saya rasa berdasarkan komentar Anda, sebaiknya Anda menggunakan loop dan recur. Ini sebenarnya tidak jauh berbeda dari apa yang Anda miliki sekarang, tetapi ini akan menghilangkan pemanggilan fungsi rekursif.

person t_scho    schedule 27.03.2015