# Finding combinations of combinations/permutations

**URL:** <https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [October 17, 2022, 7:44pm UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870 "2022-10-17T19:44:24Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![mrbaker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrbaker/32/43637_2.png) [@mrbaker](https://discourse.julialang.org/u/mrbaker)\
**Post date:** [October 17, 2022, 7:44pm UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870/1 "2022-10-17T19:44:24Z")

</div>

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:

```julia
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:

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

```

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

---

<div class="post-metadata">

**Author:** ![Geoffrey](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@Geoffrey](https://discourse.julialang.org/u/Geoffrey)\
**Post date:** [October 17, 2022, 9:06pm UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870/3 "2022-10-17T21:06:40Z")

</div>

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

```julia
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)

```

---

<div class="post-metadata">

**Author:** ![qwerty](https://avatars.discourse-cdn.com/v4/letter/q/4491bb/32.png) [@qwerty](https://discourse.julialang.org/u/qwerty)\
**Post date:** [October 17, 2022, 9:25pm UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870/4 "2022-10-17T21:25:20Z")

</div>

```julia
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]

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [October 17, 2022, 9:52pm UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870/5 "2022-10-17T21:52:20Z")

</div>

```julia
[[(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"]`:

```julia
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"]`:

```julia
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:

```julia
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) )`.

---

<div class="post-metadata">

**Author:** ![Jakub\_Wronowski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakub_wronowski/32/204030_2.png) [@Jakub\_Wronowski](https://discourse.julialang.org/u/Jakub_Wronowski)\
**Post date:** [October 18, 2022, 1:47am UTC](https://discourse.julialang.org/t/finding-combinations-of-combinations-permutations/88870/6 "2022-10-18T01:47:12Z")

</div>

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.

```julia
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
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"]]

```