Что такое Clojure для реализации for-loop?

Question

В этом вопросе вам задано значение V и список уникальных целых чисел. Ваша задача - найти количество различных подмножеств размера 4, которые суммируются с V. Каждый элемент в списке может использоваться только один раз. Если ни одно из таких подмножеств не может быть найдено, вместо этого выведите 0.

Например, если целые числа являются [3, 4, 5, 6, 7, 8, 9, 10] и значение 30, выход должен быть 5. подмножества:

[3, 8, 9, 10] 
[4, 7, 9, 10] 
[5, 6, 9, 10] 
[5, 7, 8, 10] 
[6, 7, 8, 9]. 

Это не трудно решить этот вопрос, самый прямой путь к гнездо для петли четыре раза. Каков способ Clojure для этого?

Answer 1

Вот как я бы это сделал:

(ns example.solve 
    (:require [clojure.math.combinatorics :as combo])) 

(defn solve 
    [s n v] 
    (filter (comp (partial = v) 
       (partial reduce +)) 
      (combo/combinations s n))) 

I 'используя math.combinatorics в моем примере, потому что это самый простой способ получить все комбинации из 4 элементов из списка.

Ниже приведен пример использования solve: (., Фактически генерации подмножеств)

=> (solve [3 4 5 6 7 8 9 10] 4 30) 
((3 8 9 10) (4 7 9 10) (5 6 9 10) (5 7 8 10) (6 7 8 9)) 

Answer 2

Я хотел бы использовать clojure.map.combinatorics/combinations, чтобы получить все подмножества 4-элементные, а затем filter из тех, которые не суммируются до В.

Answer 3

Интересно, что эта проблема допускает (? Вдвойне) рекурсивное решение, которое включает в себя только суммирования и подсчета

Если вы смотрите на начальный элемент 3, тогда часть решения - это количество сумм, взятых из трех элементов в остальной части последовательности, где сумма равна 27, что является меньшей формой одной и той же проблемы и поэтому может быть решено рекурсивно. Нижняя часть рекурсии - это когда вы ищете суммы, полученные из 1 элемента, что сводится к простой проверке, чтобы увидеть, есть ли в списке желаемая сумма.

Другая часть решения включает в себя просмотр следующего элемента 4, поиск сумм в остальной части списка за пределы 4, равный 26, и так далее ... Эта часть также может обрабатываться рекурсивно.

Объединение этой функции как рекурсивной функции выглядит следующим образом, которое дает желаемый ответ 5 для последовательности примеров.

(defn solve [xs n len] 
    (if (seq xs) 
    (if (= len 1) 
     (if (some #{n} xs) 1 0) 
     (+ (solve (rest xs) 
       (- n (first xs)) 
       (dec len)) 
      (solve (rest xs) 
       n 
       len))) 
    0)) 

(solve [3 4 5 6 7 8 9 10] 30 4)    
;=> 5 

Answer 4

С точки зрения непосредственно отвечая на вопрос, вот как вы могли бы сделать это с помощью индексов и для цикла:

(defn solve-for [xs v] 
    (for [ndx0 (range 0   (- (count xs) 3)) 
     ndx1 (range (inc ndx0) (- (count xs) 2)) 
     ndx2 (range (inc ndx1) (- (count xs) 1)) 
     ndx3 (range (inc ndx2) (count xs)) 
     :when (= v (+ (xs ndx0) (xs ndx1) (xs ndx2) (xs ndx3)))] 
    (list (xs ndx0) (xs ndx1) (xs ndx2) (xs ndx3)))) 

FWIW, это оказывается около 70% быстрее, чем подход используя clojure.math.combinatorics, но в два раза медленнее, чем двурекурсивное решение.