Generate all unordered pairs from vector in Julia

user_143931 0
Viewed 324

I have a vector (a Base.KeySet to be precise) and I would like to iterate over all pairs of items in the vector. The simplest attempt is a nested loop

for y1 in 1:length(col)
  for y2 in y1+1:length(col)
     # do work with col[y1] and col[y2] 
  end
end

(Note that I do not care about the order of the indices within each pair, so I skip e.g. (2,1) because that's redundant with (1,2).)

I learnt I can use eachindex(col) to possibly be more efficient (or at least make the code easier to read) instead of 1:length(col) for the outer loop, but it doesn't help me for the inner loop. Is there a better way than using the manual loop above?

julia combinations iterator
2 Answers

You want the combinations function from Combinatorics.jl

help?> combinations
search: combinations multiset_combinations CoolLexCombinations with_replacement_combinations

  combinations(a, n)

  Generate all combinations of n elements from an indexable object a. Because the number of
  combinations can be very large, this function returns an iterator object. Use
  collect(combinations(a, n)) to get an array of all combinations.

  ──────────────────────────────────────────────────────────────────────────────────────────────

  combinations(a)

  Generate combinations of the elements of a of all orders. Chaining of order iterators is
  eager, but the sequence at each order is lazy.

This method uses getindex, so you have to turn your Base.KeySet into an Array of whatever your key type is before doing the loop.

julia> d = Dict(:a => 1, :b => 2, :c => 3)
Dict{Symbol,Int64} with 3 entries:
  :a => 1
  :b => 2
  :c => 3

julia> for (i, j) in combinations(collect(keys(d)), 2)
       @info "Key combination" i=i j=j
       end
┌ Info: Key combination
│   i = :a
└   j = :b
┌ Info: Key combination
│   i = :a
└   j = :c
┌ Info: Key combination
│   i = :b
└   j = :c
user_158730290

Provided type of items in the keyset support isless, this is reasonably clean code

# typeof(col) <: Base.KeySet
for y1 in col
  for y2 in col
    y1 < y2 || continue
    # do work with y1 and y2 
  end
end
user_25583680
Related