Find all "pairing sets", such that all elements have a pair, and no pairs contain common elements

Question

I am currently trying to solve the following problem.

I must find all pairs of a set (with even number of elements) such that:

1. No two pairs have common elements
2. All elements are in a pair

As an example:

pairingsSet({0, 1, 2, 3})
should return something like
{
    {{0, 1}, {2, 3}},
    {{0, 2}, {1, 3}},
    {{0, 3}, {1, 2}},
}

And a more verbose example:

pairingsSet({0, 1, 2, 3, 4, 5})
should return something like
{
    {{0, 1}, {2, 3}, {4, 5}},
    {{0, 1}, {2, 4}, {3, 5}},
    {{0, 1}, {2, 5}, {3, 4}},
    {{0, 2}, {1, 3}, {4, 5}},
    {{0, 2}, {1, 4}, {3, 5}},
    ...
    {{0, 5}, {1, 3}, {2, 4}},
    {{0, 5}, {1, 4}, {2, 3}},
}

I can tell that the easiest way to solve this problem is with recursion, but I can't quite get my finger on how to do it.

I ordered the sets above because it helped me think of a solution, but the order does not matter. I still can't quite put my finger on a solution. I will likely be figuring out the answer soon, I made this question in case anyone else encountered a similar problem. If anyone figures out an alternative answer though, I would love to see it!

(I am currently working on a solution in Go although solutions in other languages are very much welcome)

Answer 1

Here is my solution in Go:

func allPairingSetsForAlphabet(alphabet []int) [][][2]int {
    if len(alphabet) == 2 {
        return [][][2]int{{{alphabet[0], alphabet[1]}}}
    }

    first := alphabet[0]
    rest := alphabet[1:]
    var pairingsSet [][][2]int
    for i, v := range rest {
        pair := [2]int{first, v}
        withoutV := make([]int, len(rest)-1)
        copy(withoutV[:i], rest[:i])
        copy(withoutV[i:], rest[i+1:])

        // recursive call
        otherPairingsSet := allPairingSetsForAlphabet(withoutV)
        for _, otherPairings := range otherPairingsSet {
            thisPairing := make([][2]int, len(otherPairings)+1)
            thisPairing[0] = pair
            copy(thisPairing[1:], otherPairings)
            pairingsSet = append(pairingsSet, thisPairing)
        }
    }
    return pairingsSet
}

Essentially it performs the following steps:

1. If there are only two remaining things in the alphabet, we return a pairing set containing only those two pairs (ie {{{0, 1}}})
2. Pick an element (we will call it first)
3. Makes a new set which contains all elements of the alphabet, without first (we will call this rest)
4. For each element (v) in rest, we:
   1. Make a pair of {first, v} (we will call this pair)
   2. Create a subset of rest which contains all elements in rest except v (we will call this withoutV)
   3. We make a recursive call, allPairingsForAlphabet(withoutV)
   4. For each pairing (pairing) that this call returns, we add {pair} U pairing to the result.