0

我用任何命令式语言实现这个算法都没有问题，但我正在努力用 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

4

1 回答 1

1

您的代码存在根本问题：

  • 你的start-list绑定是一个数字，不能conj编辑到'
  • 您正在调用assoc并忽略返回值，从而使其成为无操作。
  • 您正在使用for它，就好像它是一个循环构造（它是一个列表理解）
  • 你正在调用nth一个哈希映射，它总是会失败（zipmap返回一个哈希映射）

一般来说，函数式编程的想法是将可变变量提升为不可变的局部绑定，方法是使“世界状态”完全由函数参数封装，并使用该状态的改进版本进行函数调用。

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

(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- 所有数据都在本地绑定并传递给下一个用户。

于 2014-05-29T17:23:30.080 回答