ฉันควร/ฉันสามารถใช้ `assoc` ในฟังก์ชันนี้เพื่อกำหนดอาร์กิวเมนต์ของฟังก์ชันใหม่ได้หรือไม่

ฉันกำลังใช้อัลกอริทึม Bron-Kerbosch ใน 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 ไม่มีความรู้สึกของ "set 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) จะไม่แก้ไข someSet คุณก็แค่มีเซตใหม่   -  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 Bron-Kerbosch จะต้องมีฟังก์ชันตัวช่วยเพื่อให้สามารถส่งคืน cliques พร้อมกับค่าใหม่เป็น p และ x ให้กับผู้เรียก หรือเพียงแค่ส่งคืน cliques สำหรับกรณีระดับบนสุด - person noisesmith; 28.03.2015

arrow_upward
0
arrow_downward

ฉันคิดว่าจากความคิดเห็นของคุณ คุณควรใช้ loop และ recur จะดีกว่า มันไม่ได้แตกต่างไปจากที่คุณมีตอนนี้มากนัก แต่มันจะกำจัดการเรียกใช้ฟังก์ชันแบบเรียกซ้ำ

person t_scho    schedule 27.03.2015