algorithm - 在函数范式中实现 Karger 的最小割算法

Question

我在任何命令式语言中实现这个算法都没有问题，但我在 Clojure 或任何其他函数式语言中很难实现它。许多算法都是根据使用可变数据结构和命令式循环来描述的，我很难将所有这些都转换为功能域。

这是我使用邻接列表作为图形表示在 Clojure 中实现它的不完整尝试(草稿，不是工作实现):

(ns karger.core
  (:require [clojure.string :as string]))

(defn load-data []
    (zipmap 
     (range 1 1000)
     (map rest (map read-string
       (string/split (slurp "data.txt") #"\n")))))

(defn min-cut [graph] 
  (let [start (rand-int (count graph))
        end (rand-int (graph start))
        start-list (nth graph start)]
    (for [x (graph end)
          :when (not= x start)]
      (assoc graph start (conj start-list x)))
      ))

(count (load-data))

谁能给我一个这个算法的引用实现(最好是用Clojure写的)？另外，如果有人给我一个一般性的建议，我希望将命令式术语中描述的算法转换为功能域。

提前致谢!

更新 #1

这是用 Python 编写的算法实现的链接:http://pastebin.com/WwWCtxpu

Answer 1

您的代码存在基本问题:

• 你的 start-list 绑定(bind)是一个数字，不能被conjed '
• 您正在调用 assoc 并忽略返回值，因此使其成为空操作。
• 你正在使用 for 就好像它是一个循环结构(它是一个列表理解)
• 您在 HashMap 上调用 nth，这总是会失败(zipmap 返回一个 HashMap )

一般而言，函数式编程的思想是通过使“世界状态”完全由函数参数封装，并使用该状态的改进版本进行函数调用，将可变变量提升为不可变局部绑定(bind)。

这是一个基于您发布的 python 解决方案以及 java 示例使用的图形文件的从头开始的工作实现 here

(ns min-cut.core
  (:require [clojure.java.io :as io]
            [clojure.string :as string]
            [clojure.pprint :refer [pprint]]))

(defn make-maps
  [filename]
  (reduce (fn [graph line]
            (let [[node & edges] (->> line
                                      (#(string/split % #"\W+"))
                                      (remove #{""})
                                      (map read-string))]
              (assoc graph node (set edges))))
          {}
          (line-seq (io/reader filename))))

(defn karger
  [graph]
  (if (<= (count (keys graph))
          2)
    (count (graph (apply min (keys graph))))
    (let [start (rand-nth (keys graph))
          finish (rand-nth (vec (graph start)))
          graph (loop [g graph
                       [edge & edges] (seq (graph finish))]
                  (if-not edge
                    g
                    (recur
                     (if (= edge start)
                       g
                       (update-in g [start] conj edge))
                     edges)))
          graph (loop [g graph
                       [edge & edges] (seq (graph finish))]
                  (if-not edge
                    g
                    (let [gr (update-in g [edge] disj finish)
                          gr (if (= edge start)
                               gr
                               (update-in gr [edge] conj start))]
                      (recur gr edges))))
          graph (dissoc graph finish)]
      (recur graph))))

(defn -main
  [& [file]]
  (let [file (or file "kargerAdj.txt")
        graph (make-maps file)]
    (println "min cut is: "
             (reduce min (repeatedly 1801 #(karger graph))))))

这是对 python 代码的直译，因此该代码有多个地方可以改进。对于初学者来说，karger 函数中的两个循环可能会被单个 reduce 代替，这样会更加简洁明了。

请注意，在此代码中创建的任何值都不会发生变化 - 值会反弹，但不会更改任何传入的数据结构，唯一使用的全局定义是函数 make-maps， karger 和 -main - 所有数据都在本地绑定(bind)并传递给下一个用户。