3Sum utilisant pour dans Clojure

Question

J'ai eu cet exercice algo classique: Combien de triplets somme à zéro dans ce tableau? Pas de problème en Java application du présent:

int count = 0; 
for (int i = 0; i < array.length - 2; i++) { 
    (for int j= i+1; j < array.length -1; j++) { 
    (for int k = j + 1; k < array.length; k++) { 
     if (array[i] + array[j] + array[k] == 0) { 
     count++; 
     } 
    } 
    } 
} 
return count; 

Comment pourrais-je faire cela en Clojure bien? Je me suis demandé: Comment puis-je faire des boucles imbriquées à Clojure.

Mais this question and answer ne résout pas vraiment mon problème, car il prend deux tableaux identiques et combine tous les éléments (également les éléments identiques, par exemple 1 et 1).

Question connexe: Comment obtenir toutes les combinaisons de triplets d'une collection?

Remarque: Il nous a été explicitement demandé de ne pas trier le tableau. Je sais qu'il existe des algorithmes plus rapides pour cela.

EDIT: Ajout de «== 0» à la condition.

Answer 1

aussi vous pouvez le faire avec la compréhension de la liste, sans indices d'exploitation du tout:

user> (def data [1 -2 1 1 -3 2]) 
#'user/data 

user> (defn tails [data] 
     (take-while seq (iterate rest data))) 
#'user/tails 

user> (for [[x & xs] (tails data) 
      [y & ys] (tails xs) 
      [z] (tails ys) 
      :when (zero? (+ x y z))] 
     [x y z]) 

;;=> ([1 -2 1] [1 -2 1] [1 -3 2] [-2 1 1] [1 -3 2] [1 -3 2]) 

Answer 2

Vous pouvez utiliser la boucle for dans clojure, de la même manière que dans Java.

1. Calculer que le nombre de combinaisons cette somme à 0,

(defn three-sum-count [array] 
    (let [three_sum 
     (for [i (range 0 (- (count array) 2)) 
       j (range (+ 1 i) (- (count array) 1)) 
       k (range (+ 1 j) (count array))] 
      (if (zero? (+ (get array i) (get array j) (get array k))) 1 0))] 
    (reduce + three_sum))) 

Exemples de REPL,

user=> (three-sum-count [1, -2]) 
0 
user=> (three-sum-count [1, -2, 1]) 
1 
user=> (three-sum-count [1, -2, 1, 1]) 
3 
user=> (three-sum-count [1 -2 1 1 -3 2]) 
6 

2. Liste toutes les combinaisons de cette somme à zéro,

(defn three-sum-combinations [array] 
    (remove empty? 
      (for [i (range 0 (- (count array) 2)) 
       j (range (+ 1 i) (- (count array) 1)) 
       k (range (+ 1 j) (count array))] 
      (if (zero? (+ (get array i) (get array j) (get array k))) 
       [(get array i) (get array j) (get array k)] 
       [])))) 

Exemples de REPL

user=> (three-sum-combinations [1, -2]) 
() 
user=> (three-sum-combinations [1, -2, 1]) 
([1 -2 1]) 
user=> (three-sum-combinations [1, -2, 1, 1]) 
([1 -2 1] [1 -2 1] [-2 1 1]) 
user=> (three-sum-combinations [1 -2 1 1 -3 2]) 
([1 -2 1] [1 -2 1] [1 -3 2] [-2 1 1] [1 -3 2] [1 -3 2]) 

vous pouvez également calculer combien de combinaisons de cette façon,

user=> (count (three-sum-combinations [1 -2 1 1 -3 2])) 
6