#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])
Комментарии:
1. Я только что понял (поскольку StackOverflow изменил порядок ответов кандидатов на странице), что это очень небольшое обобщение решения @mikera, приведенного ниже.
Ответ №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])