查找总和为n的整数集合的所有子集

Question

我试图找到一个函数，给定S是一个整数集，I是一个整数，返回S的所有子集，求和为I

在clojure-contrib或其他库中有这样的函数吗？

如果没有，谁能给我一些提示，让我用clojure的方式编写它？

Answer 1

这不是subset sum problem，一个典型的NP完全问题吗？

在这种情况下，我将生成S的每个可能的不同子集，并查看哪些子集和为I。

Answer 2

我认为这是子集求和问题，正如@MrBones所建议的那样。下面是一个使用https://github.com/clojure/math.combinatorics (lein：[org.clojure/math.combinatorics "0.0.7"])的暴力破解尝试：

(require '[clojure.math.combinatorics :as c])

(defn subset-sum [s n] 
  "Return all the subsets of s that sum to n."
  (->> (c/subsets s)
       (filter #(pos? (count %))) ; ignore empty set since (+) == 0
       (filter #(= n (apply + %)))))

(def s #{1 2 45 -3 0 14 25 3 7 15})

(subset-sum s 13)
; ((1 -3 15) (2 -3 14) (0 1 -3 15) (0 2 -3 14) (1 2 3 7) (0 1 2 3 7))
(subset-sum s 0)
; ((0) (-3 3) (0 -3 3) (1 2 -3) (0 1 2 -3))

这些“子集”就是列表。可以转换回套装，但我没有麻烦。

Answer 3

您可以生成集合的子集，如下所示：

(defn subsets [s]
  (if (seq s)
    (let [f (first s), srs (subsets (disj s f))]
      (concat srs (map #(conj % f) srs)))
    (list #{})))

这个想法是从集合s中选择一个元素:第一个元素f就可以了。然后我们递归地找到其他所有东西的子集，srs。srs包含所有不含f的子集。通过向每个子集添加f，我们可以使用f获得所有子集。总而言之，这就是全部。最后，如果我们不能选择一个元素，因为没有任何元素，那么唯一的子集就是空的。

剩下要做的就是从所有子集中筛选出和为n的子集。用于测试这一点的函数是

(fn [s] (= n (reduce + s)))

它不值得命名。

把这些放在一起，我们想要的函数是

(defn subsets-summing-to [s n]
  (filter
    (fn [xs] (= n (reduce + xs)))
    (subsets s)))

备注

• 由于答案是一个集合序列，我们可以通过将concat改为lazy-cat来使其变得更懒惰。无论如何，map是懒惰的。
• 我们可能看起来生成了很多集合，但请记住，它们共享存储:保持另一个集合与单个元素相差的空间成本(几乎)是恒定的。在Clojure算法中，
• 将空集求和为零。