Getting unique, non-redundant combinations in Julia array?

user_5666203 0
Viewed 101

I have two arrays of variables I am comparing,

arr1 = [1,2,3]
arr2 = [1,2,3]

I would like to get each unique, non-redundant combination of variables. The initial unique combinations are:

(1,1), (1,2), (1,3)
(2,1), (2,2), (2,3)
(3,1), (3,2), (3,3)

But this set is further reduced, since comparing variable 1 with itself (and 2 with itself, etc.) is meaningless. Removing these, the set reduces to:

(1,2), (1,3)
(2,1), (2,3)
(3,1), (3,2)

Furthermore, there are redundant pairs since comparing variable 1 to variable 2 is the same as comparing variable 2 to variable 1. So the end result I'm looking for would be:

(1,2), (1,3), (2,3)

I can reason through the first bit:

# Generate combination arrays
sets = []
sy = 3
for i in 1:size(ellipseX)[2]
    set1 = repeat([i],sy)
    set2 = range(1,sy)
    newsets = cat(set1,set2,dims=2)
    sets = cat(sets,newsets,dims=1)
end
# Remove rows with same column values
for N in 0:sy-1
    rownum = 1+sy*N
    sets = sets[setdiff(1:end, rownum), :]
end

but removing the redundant pairs is a bit more tricky. Is there a much easier way to do this?

julia combinations unique
2 Answers

This seems like a job for Combinatorics.jl.

using Combinatorics

arr1 = [1,2,3]
arr2 = [1,2,3]

arr = unique([arr1; arr2])
combs = combinations(arr,2) |> collect
 [1, 2]
 [1, 3]
 [2, 3]

If, for some reason you can't install Combinatorics.jl, a comprehension will also work.

n = length(arr)
combs = [(arr[i],arr[j]) for i = 1:n-1 for j = i+1:n]
(1, 2)
(1, 3)
(2, 3)

Update: If the arrays might have different numbers, another in-place filtering operation is required to make sure the output tuples have one element taken from arr1 and the other element taken from arr2.

filter!(t->any(t .∈ (arr1,)) && any(t .∈ (arr2,)), combs)

Example:

arr1 = [1,2,3,4]
arr2 = [1,2,5]

U = unique([arr1; arr2])

n = length(U)
combs = [(U[i],U[j]) for i=1:n-1 for j=i+1:n]
filter!(t->any(t .∈ (arr1,)) && any(t .∈ (arr2,)), combs)
9-element Vector{Tuple{Int64, Int64}}:
 (1, 2)
 (1, 3)
 (1, 4)
 (1, 5)
 (2, 3)
 (2, 4)
 (2, 5)
 (3, 5)
 (4, 5)
user_39431700

I'm not sure the previous answer actually answers your question, here is my interpretation of your problem when arr1 and arr2 have different values (eg. in this example, should (3,4) be included?)

Iterators.product returns an iterator with the first part of your problem

julia> a1 = [1,2,3,4]

julia> a2 = [1,2,5]

julia> Iterators.product(a1, a2) |> collect
4×3 Matrix{Tuple{Int64, Int64}}:
 (1, 1)  (1, 2)  (1, 5)
 (2, 1)  (2, 2)  (2, 5)
 (3, 1)  (3, 2)  (3, 5)
 (4, 1)  (4, 2)  (4, 5)

then, filtering out those with repeated numbers:

julia> Iterators.filter(allunique, Iterators.product(a1, a2)) |> collect
10-element Vector{Tuple{Int64, Int64}}:
 (2, 1)
 (3, 1)
 (4, 1)
 (1, 2)
 (3, 2)
 (4, 2)
 (1, 5)
 (2, 5)
 (3, 5)
 (4, 5)

finally, you can use unique(f, itr) with Set to get the required result

julia> unique(Set, Iterators.filter(allunique, Iterators.product(a1, a2)))
9-element Vector{Tuple{Int64, Int64}}:
 (2, 1)
 (3, 1)
 (4, 1)
 (3, 2)
 (4, 2)
 (1, 5)
 (2, 5)
 (3, 5)
 (4, 5)

This solution can accept more than 2 input vectors

user_141833430
Related