Получить текущий элемент и список, содержащий все остальное в Clojure?

Question

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

Например, учитывая список (1 2 3)

Я хочу получить список ((1 (2 3)) (2 (1 3)) (3 (1 2)))

Спасибо за вашу помощь!

Answer 1

Это будет работать без обхода всего вектора снова и снова:

(defn this-and-that [xs]
  (map-indexed (fn [i x]
                [x (concat (take i xs) 
                           (drop (inc i) xs))])
              xs))

, а также работает для nils:

user=> (this-and-that [1 2 nil 3])
([1 (2 nil 3)] [2 (1 nil 3)] [nil (1 2 3)] [3 (1 2 nil)])

Answer 2

Другие ответы дают хорошие способы сделать это, однако то, что вы описываете, по сути является операцией O (n ^ 2), предполагая, что вы на самом деле понимаете все ленивые последовательности и т. Д. Это, вероятно, не будет хорошей идеей, еслиn> = 1 000 000

Возможно, вы захотите расширить область кода, который вы рассматриваете, чтобы увидеть, сможете ли вы найти более эффективный алгоритм в целом.

Например, вы можете обнаружить, чтоЛучше всего преобразовать весь список в вектор и написать свой алгоритм с точки зрения индексированного доступа в вектор.

Answer 3

"миллион элементов" это не много.Попробуйте, если это достаточно быстро:

(defn this-and-that
  [s]
  (map-indexed (fn [i el]
                 [el (keep-indexed #(if (= %1 i)
                                            nil
                                            %2) s)]) s))

Пример:

user> (this-and-that [1 2 3])
([1 (2 3)] [2 (1 3)] [3 (1 2)])

Обратите внимание, что этот код не работает правильно для последовательностей, содержащих nil.

Answer 4

Как насчет использования наборов?

user> (let [xs #{1 2 3}]
        (for [x xs] [x (disj xs x)]))
([1 #{2 3}] [2 #{1 3}] [3 #{1 2}])

Делать это на съемочной площадке с миллионами предметов не так уж плохо по времени:

(let [xs (set (range 1000000))]
  (time (count (for [x xs] [x (disj xs x)]))))
"Elapsed time: 841.668 msecs"
1000000