# Finding combinations of combinations/permutations

I’m trying to generate a list of combinations of combinations for an array.

First, I’d like to find all pairs that don’t reuse elements (order doesn’t matter), and I’ve been able to get that far:

``````using Combinatorics

a = ["a", "b", "c", "d"]

c = Combinatorics.combinations(a, 2)

julia> collect(c)
6-element Vector{Vector{String}}:
["a", "b"]
["a", "c"]
["a", "d"]
["b", "c"]
["b", "d"]
["c", "d"]
``````

From this set of pairs, I’d then like to find all combinations of these pairs that contain (but do not repeat) every element (so, total number of pairs is `length(a)/2` – in this case, 2). The order of the pairs doesn’t matter. I would like the final output to be something like this:

``````[["a", "b"], ["c", "d"]]
[["a", "c"], ["b", "d"]]
[["a", "d"], ["b", "c"]]
``````

but I’m not sure how to get there. Any suggestions?

This might not be the best solution but here is a way to do it:

``````a = ["a", "b", "c", "d"]

c = Combinatorics.combinations(a, 2)

d = Iterators.filter(i -> length(unique(cat(i..., dims = 1))) == 4, Combinatorics.combinations(collect(c), 2))

collect(d)
``````
``````c = Set(Set.(combinations(a, 2)))
A = Set(a)
r = Set((Set([i, setdiff(A, i)]) for i in c if setdiff(A, i) in c))
r = [collect.(i) for i in r]
``````
``````[[(p[i],p[i+1]) for i in 1:2:length(a)] for p in permutations(a)
if all(p[1:2:end-2] .< p[3:2:end]) && all(p[1:2:end] .< p[2:2:end])]
``````

gives for `a = ["a", "b", "c", "d"]`:

``````3-element Vector{Vector{Tuple{String, String}}}:
[("a", "b"), ("c", "d")]
[("a", "c"), ("b", "d")]
[("a", "d"), ("b", "c")]
``````

and gives for `a = ["a", "b", "c", "d", "e", "f"]`:

``````15-element Vector{Vector{Tuple{String, String}}}:
[("a", "b"), ("c", "d"), ("e", "f")]
[("a", "b"), ("c", "e"), ("d", "f")]
[("a", "b"), ("c", "f"), ("d", "e")]
[("a", "c"), ("b", "d"), ("e", "f")]
[("a", "c"), ("b", "e"), ("d", "f")]
[("a", "c"), ("b", "f"), ("d", "e")]
[("a", "d"), ("b", "c"), ("e", "f")]
[("a", "d"), ("b", "e"), ("c", "f")]
[("a", "d"), ("b", "f"), ("c", "e")]
[("a", "e"), ("b", "c"), ("d", "f")]
[("a", "e"), ("b", "d"), ("c", "f")]
[("a", "e"), ("b", "f"), ("c", "d")]
[("a", "f"), ("b", "c"), ("d", "e")]
[("a", "f"), ("b", "d"), ("c", "e")]
[("a", "f"), ("b", "e"), ("c", "d")]
``````

The comprehension basically goes over all permutations and gets single representative from each equivalence group of the solution’s symmetry group (if math lingo unclear, the actual one-liner is simpler to understand).

But perhaps a simple recursive function is quicker:

``````function trans(a)
n = length(a)
# next two conditions can be commented out as they shouldn't
# occur in normal usage
n == 0 && return Vector{Tuple{eltype(a),eltype(a)}}[]
isodd(n) && error("must be even length")
n == 2 && return [(a[1], a[2])]
res = Vector{Tuple{eltype(a),eltype(a)}}[]
for i=2:n
append!(res,
vcat((a[1],a[i]),t) for t in trans([a[j] for j=2:n if j ≠ i]))
end
return res
end
``````

If optimization really critical, preallocation possible using formula for number of elements: `result_length = factorial(n) / ( factorial(n÷2) * 2^(n÷2) )`.

1 Like

This have a simple interpretation. First select 2 elements, then select another 2 from elements to the right from previously selected. It looks like you want to generate all partitions which have size 2,2,N-4.
I think in Knuth’s book you will find effective algorithms. google for “taocp generating all partitions”, first result should download the book.

``````function solution(input, n)
result = Vector{Vector{eltype(input)}}[]
N = length(input)
first_selections = combinations(1:N-n, n)
for first_selection in first_selections
second_selections = combinations((last(first_selection)+1):N, n)
for second_selection in second_selections
push!(result, [input[first_selection], input[second_selection]])
end
end
result
end
``````
``````julia> input = ["a", "b", "c", "d", "e"];

julia> solution(input, 2)
5-element Vector{Vector{Vector{String}}}:
[["a", "b"], ["c", "d"]]
[["a", "b"], ["c", "e"]]
[["a", "b"], ["d", "e"]]
[["a", "c"], ["d", "e"]]
[["b", "c"], ["d", "e"]]
``````
1 Like