Finding combinations of combinations/permutations

New to Julia
1

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?

3

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)
4 
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]
5 
[[(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
6

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