найти все подмножества в коллекции целого, который суммирует п

Question

я пытаюсь найти функцию, которая, учитывая S набор целого числа, и я целое, вернуть все подмножества 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.