Идиоматический способ перебора всех пар коллекции в Clojure

ProgramBox

Идиоматический способ перебора всех пар коллекции в Clojure

Post author:admin
Запись опубликована:29 мая, 2023
Post category:Вопросы по программированию

#clojure #sequence

#clojure #последовательность

Вопрос:

Учитывая коллекцию, я хочу перебрать все пары в коллекции. Пример

 (all-pairs seq)

(all-pairs '(a b c d)) => ([a b] [a c] [a d] [b c] [b d] [c d]))

Вот моя идея

 (defn all-pairs [coll]
  (for [ [idx elmt] (indexed coll)
         other-elmt (subvec coll (inc idx))]
     (vector elmt other-elm)))

Но это не кажется идиоматичным

Ответ №1:

Как насчет:

 (use 'clojure.contrib.combinatorics)
(vec (map vec (combinations '(a b c d) 2)))

1. извините, не распознал, что внешний контейнер представляет собой список. Итак, правильная версия (map vec (combinations ‘(a b c d) 2))

2. clojure.contrib.combinatorics перенесено в clojure.math.combinatorics : clojure.github.io/math.combinatorics

Ответ №2:

Ленивый и относительно быстрый.

 (defn all-pairs [coll]
  (when-let [s (next coll)]
    (lazy-cat (for [y s] [(first coll) y])
              (all-pairs s))))

 (defn all-pairs [coll]
  (let [x (first coll) xs (next coll)]
    (when xs
      (lazy-cat
       (map (fn [y] [x y]) xs) 
       (all-pairs xs)))))

(all-pairs [1 2 3 4])
;; => ([1 2] [1 3] [1 4] [2 3] [2 4] [3 4])

(all-pairs '(a b c d))
;; => ([a b] [a c] [a d] [b c] [b d] [c d])

Ответ №3:

 (defn all-pairs [coll]
  (loop [[x amp; xs] coll
         result []]
    (if (nil? xs)
      result
      (recur xs (concat result (map #(vector x %) xs))))))

1. Если возникает проблема с производительностью, замена на concat на apply conj значительно ускорит процесс.

2. потрясающе! я искал идиоматический для … каждого, деструктурирование параметра x в цикле — отличная идея! Спасибо

Ответ №4:

Могу ли я предложить:

 (defn all-pairs [sq] (for [i sq j sq] [i j]))

РЕДАКТИРОВАТЬ: Очевидно, я неправильно истолковал вопрос; поскольку вам нужны только отдельные не дублирующиеся пары, мы все еще можем использовать этот подход, если существует естественный порядок в любом домене, в котором вы вызываете эту функцию.

 (defn all-pairs [sq] (filter #(< (first %) (second %)) (for [i sq j sq] [i j])))

ПРАВКА 2

Также:

 (defn all-pairs [sq]
    (partition 2 (flatten (map (fn [sqi] (map #(vector %1 %2) sq sqi))
                   (take-while not-empty (iterate rest (rest sq)))))))

1. Одна из проблем заключается в том, что сюда входят такие термины, как [b a] и [a a], которые, судя по описанию, включать не следует.

2. Да, это была моя первоначальная идея, но она включает [b a] и [a b]. Я хочу только одного.

3. Мне нравится решение for, использующее when для фильтрации дубликатов: (for [a col, b col, :when (> (int a) (int b))] [a b])

4. используйте < для более естественного результата: ;;=> ([1 2] [1 3] [2 3]) vs ;;=> ([2 1] [3 1] [3 2])

Ответ №5:

Если вы хотите написать свою собственную combinations функцию в «академическом стиле», вы можете попробовать

 (defn comb [xs m]
  (cond
    (= m 0) (list ())
    (empty? (seq xs)) ()
    :else (let [x (first xs)
                xs (rest xs)]
            (concat
             (map #(cons x %) (comb xs (- m 1)))
             (comb xs m)))))

а затем примените его к вашей проблеме следующим образом

 (map vec (comb '(a b c d) 2))

 ([a b] [a c] [a d] [b c] [b d] [c d])

Ответ №6:

Простая рекурсивная версия, которая должна делать то, что вы хотите:

 (defn all-pairs [coll]
  (let [x (first coll)
        xs (rest coll)]
    (if (empty? xs) 
      nil
      (concat 
        (map (fn [y] [x y]) xs) 
        (all-pairs xs)))))

1. Я думаю, что вы хотите выполнить свой рекурсивный вызов с помощью (recur xs), а не (all-pairs xs).

2. Ну, это не обязательно, но стек взорвется.

3. @Rob — конечно, recur здесь не сработает, поскольку это не конечная рекурсивная позиция?

4. Вы правы. У меня явно не очень удачный день с пониманием прочитанного. Я также не вижу простого способа сделать это хвостовой рекурсией.

Ответ №7:

Не самое быстрое решение, но:

 ; handy helper function
(defn tails [v]
  "Given a sequence ( a b c ), returns all tails:  ( a b c ) ( b c ) ( c )"
  (when (seq v) 
    (lazy-cat (list v) (tails (rest v)))))

(defn pair* [v]
  "Match the first item in the list with all others in pairs."
  (when (> (count v) 1)
    (for [y v] [(first v) y])))

(defn all-pairs [v]
  (apply concat (map pair* (tails v))))

Ответ №8:

Как насчет этого?

 (defn all-pairs [coll]
(when coll
  (concat (map vector (repeat (first coll)) (rest coll))
          (all-pairs (next coll)))))

Или, если вы ищете отложенный seq:

 (defn all-pairs [coll]
(lazy-seq
  (when coll
    (concat (map vector (repeat (first coll)) (rest coll))
            (all-pairs (next coll))))))

Ответ №9:

Как насчет этого?

 (defn seq->pairs 
  [s]
  (loop [res [] s s]
     (let [[head next] (split-at 2 s)
           res (conj res head)]
        (if (empty? next) res (recur res next)))))

Ответ №10:

Просто еще одно возможное решение:

 (defn all-pairs
        [c]
        (mapcat #(drop % %2)
                 (range 1 (count c))
                 (partition (count c) (for [a c b c] [a b]))))


(all-pairs '(a b c d)) => ([a b] [a c] [a d] [b c] [b d] [c d]))
(all-pairs [5 4 3 2 1]) => ([5 4] [5 3] [5 2] [5 1] [4 3] [4 2] [4 1] [3 2] [3 1] [2 1])
(all-pairs "pairs") => ([p a] [p i] [p r] [p s] [a i] [a r] [a s] [i r] [i s] [r s])