Get current item and list containing everything else in Clojure?

Question

What is the fastest way to get a list containing pairs of the current item with a list containing all the other items? This should be quick, as the list may contain a million items or more.

For example, given the list (1 2 3)

I want to get the list ((1 (2 3)) (2 (1 3)) (3 (1 2)))

Thank you for your help!

Answer 1

This will work without moving the entire vector over and over:

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

and also works for 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

"million elements" are not many. Try it if it's fast enough:

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

Example:

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

Please note that this code does not work correctly for seqs containing nil .

Answer 3

Other answers give good ways to do this, however, what you are describing is basically an O (n ^ 2) operation, assuming you are really implementing all the lazy sequences, etc. It probably would not be a good idea if n> = 1,000,000

Perhaps you should consider expanding the scope of the code that you plan to see if you can find a more efficient algorithm in general.

For example, you may find that it is best to convert the entire list to a vector and write your algorithm in terms of indexed access into a vector.

Answer 4

How about using kits?

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

Doing this in a set with a million elements is not so bad in time:

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