# Every possible pairing

Given an positive even integer $$\ n \$$, output the set of "ways to pair up" the set $$\ [1, n] \$$. For example, with $$\ n = 4 \$$, we can pair up the set $$\ \{1, 2, 3, 4\} \$$ in these ways:

• $$\ \{\{1, 2\}, \{3, 4\}\} \$$
• $$\ \{\{1, 3\}, \{2, 4\}\} \$$
• $$\ \{\{1, 4\}, \{2, 3\}\} \$$

This can more formally be described as the set of sets of pairs of integers such that those pairs exactly cover the set $$\ [1, n] \$$.

Note that because we're dealing with sets here, the order of the pairs is irrelevant. For example, $$\ \{\{1, 2\}, \{3, 4\}\} \$$ is considered the same as $$\ \{\{3, 4\},\{2, 1\}\} \$$.

For the same reason, the order of your output does not matter. However, your output may not contain duplicates.

• If you want, you can choose to operate on the set $$\ [0, n) \$$ instead of $$\ [1, n] \$$
• If you want, you can choose to take the integer $$\ \frac n 2 \$$ as input, instead of $$\ n \$$

This is , so the shortest code in bytes wins.

## Test cases

2 -> {{{1, 2}}}
4 -> {{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}}
6 -> {{{1, 2}, {3, 4}, {5, 6}}, {{1, 2}, {3, 5}, {4, 6}}, {{1, 2}, {3, 6}, {4, 5}}, {{1, 3}, {2, 4}, {5, 6}}, {{1, 3}, {2, 5}, {4, 6}}, {{1, 3}, {2, 6}, {4, 5}}, {{1, 4}, {2, 3}, {5, 6}}, {{1, 4}, {2, 5}, {3, 6}}, {{1, 4}, {2, 6}, {3, 5}}, {{1, 5}, {2, 3}, {4, 6}}, {{1, 5}, {2, 4}, {3, 6}}, {{1, 5}, {2, 6}, {3, 4}}, {{1, 6}, {2, 3}, {4, 5}}, {{1, 6}, {2, 4}, {3, 5}}, {{1, 6}, {2, 5}, {3, 4}}}
8 -> {{{1, 2}, {3, 4}, {5, 6}, {7, 8}}, {{1, 2}, {3, 4}, {5, 7}, {6, 8}}, {{1, 2}, {3, 4}, {5, 8}, {6, 7}}, {{1, 2}, {3, 5}, {4, 6}, {7, 8}}, {{1, 2}, {3, 5}, {4, 7}, {6, 8}}, {{1, 2}, {3, 5}, {4, 8}, {6, 7}}, {{1, 2}, {3, 6}, {4, 5}, {7, 8}}, {{1, 2}, {3, 6}, {4, 7}, {5, 8}}, {{1, 2}, {3, 6}, {4, 8}, {5, 7}}, {{1, 2}, {3, 7}, {4, 5}, {6, 8}}, {{1, 2}, {3, 7}, {4, 6}, {5, 8}}, {{1, 2}, {3, 7}, {4, 8}, {5, 6}}, {{1, 2}, {3, 8}, {4, 5}, {6, 7}}, {{1, 2}, {3, 8}, {4, 6}, {5, 7}}, {{1, 2}, {3, 8}, {4, 7}, {5, 6}}, {{1, 3}, {2, 4}, {5, 6}, {7, 8}}, {{1, 3}, {2, 4}, {5, 7}, {6, 8}}, {{1, 3}, {2, 4}, {5, 8}, {6, 7}}, {{1, 3}, {2, 5}, {4, 6}, {7, 8}}, {{1, 3}, {2, 5}, {4, 7}, {6, 8}}, {{1, 3}, {2, 5}, {4, 8}, {6, 7}}, {{1, 3}, {2, 6}, {4, 5}, {7, 8}}, {{1, 3}, {2, 6}, {4, 7}, {5, 8}}, {{1, 3}, {2, 6}, {4, 8}, {5, 7}}, {{1, 3}, {2, 7}, {4, 5}, {6, 8}}, {{1, 3}, {2, 7}, {4, 6}, {5, 8}}, {{1, 3}, {2, 7}, {4, 8}, {5, 6}}, {{1, 3}, {2, 8}, {4, 5}, {6, 7}}, {{1, 3}, {2, 8}, {4, 6}, {5, 7}}, {{1, 3}, {2, 8}, {4, 7}, {5, 6}}, {{1, 4}, {2, 3}, {5, 6}, {7, 8}}, {{1, 4}, {2, 3}, {5, 7}, {6, 8}}, {{1, 4}, {2, 3}, {5, 8}, {6, 7}}, {{1, 4}, {2, 5}, {3, 6}, {7, 8}}, {{1, 4}, {2, 5}, {3, 7}, {6, 8}}, {{1, 4}, {2, 5}, {3, 8}, {6, 7}}, {{1, 4}, {2, 6}, {3, 5}, {7, 8}}, {{1, 4}, {2, 6}, {3, 7}, {5, 8}}, {{1, 4}, {2, 6}, {3, 8}, {5, 7}}, {{1, 4}, {2, 7}, {3, 5}, {6, 8}}, {{1, 4}, {2, 7}, {3, 6}, {5, 8}}, {{1, 4}, {2, 7}, {3, 8}, {5, 6}}, {{1, 4}, {2, 8}, {3, 5}, {6, 7}}, {{1, 4}, {2, 8}, {3, 6}, {5, 7}}, {{1, 4}, {2, 8}, {3, 7}, {5, 6}}, {{1, 5}, {2, 3}, {4, 6}, {7, 8}}, {{1, 5}, {2, 3}, {4, 7}, {6, 8}}, {{1, 5}, {2, 3}, {4, 8}, {6, 7}}, {{1, 5}, {2, 4}, {3, 6}, {7, 8}}, {{1, 5}, {2, 4}, {3, 7}, {6, 8}}, {{1, 5}, {2, 4}, {3, 8}, {6, 7}}, {{1, 5}, {2, 6}, {3, 4}, {7, 8}}, {{1, 5}, {2, 6}, {3, 7}, {4, 8}}, {{1, 5}, {2, 6}, {3, 8}, {4, 7}}, {{1, 5}, {2, 7}, {3, 4}, {6, 8}}, {{1, 5}, {2, 7}, {3, 6}, {4, 8}}, {{1, 5}, {2, 7}, {3, 8}, {4, 6}}, {{1, 5}, {2, 8}, {3, 4}, {6, 7}}, {{1, 5}, {2, 8}, {3, 6}, {4, 7}}, {{1, 5}, {2, 8}, {3, 7}, {4, 6}}, {{1, 6}, {2, 3}, {4, 5}, {7, 8}}, {{1, 6}, {2, 3}, {4, 7}, {5, 8}}, {{1, 6}, {2, 3}, {4, 8}, {5, 7}}, {{1, 6}, {2, 4}, {3, 5}, {7, 8}}, {{1, 6}, {2, 4}, {3, 7}, {5, 8}}, {{1, 6}, {2, 4}, {3, 8}, {5, 7}}, {{1, 6}, {2, 5}, {3, 4}, {7, 8}}, {{1, 6}, {2, 5}, {3, 7}, {4, 8}}, {{1, 6}, {2, 5}, {3, 8}, {4, 7}}, {{1, 6}, {2, 7}, {3, 4}, {5, 8}}, {{1, 6}, {2, 7}, {3, 5}, {4, 8}}, {{1, 6}, {2, 7}, {3, 8}, {4, 5}}, {{1, 6}, {2, 8}, {3, 4}, {5, 7}}, {{1, 6}, {2, 8}, {3, 5}, {4, 7}}, {{1, 6}, {2, 8}, {3, 7}, {4, 5}}, {{1, 7}, {2, 3}, {4, 5}, {6, 8}}, {{1, 7}, {2, 3}, {4, 6}, {5, 8}}, {{1, 7}, {2, 3}, {4, 8}, {5, 6}}, {{1, 7}, {2, 4}, {3, 5}, {6, 8}}, {{1, 7}, {2, 4}, {3, 6}, {5, 8}}, {{1, 7}, {2, 4}, {3, 8}, {5, 6}}, {{1, 7}, {2, 5}, {3, 4}, {6, 8}}, {{1, 7}, {2, 5}, {3, 6}, {4, 8}}, {{1, 7}, {2, 5}, {3, 8}, {4, 6}}, {{1, 7}, {2, 6}, {3, 4}, {5, 8}}, {{1, 7}, {2, 6}, {3, 5}, {4, 8}}, {{1, 7}, {2, 6}, {3, 8}, {4, 5}}, {{1, 7}, {2, 8}, {3, 4}, {5, 6}}, {{1, 7}, {2, 8}, {3, 5}, {4, 6}}, {{1, 7}, {2, 8}, {3, 6}, {4, 5}}, {{1, 8}, {2, 3}, {4, 5}, {6, 7}}, {{1, 8}, {2, 3}, {4, 6}, {5, 7}}, {{1, 8}, {2, 3}, {4, 7}, {5, 6}}, {{1, 8}, {2, 4}, {3, 5}, {6, 7}}, {{1, 8}, {2, 4}, {3, 6}, {5, 7}}, {{1, 8}, {2, 4}, {3, 7}, {5, 6}}, {{1, 8}, {2, 5}, {3, 4}, {6, 7}}, {{1, 8}, {2, 5}, {3, 6}, {4, 7}}, {{1, 8}, {2, 5}, {3, 7}, {4, 6}}, {{1, 8}, {2, 6}, {3, 4}, {5, 7}}, {{1, 8}, {2, 6}, {3, 5}, {4, 7}}, {{1, 8}, {2, 6}, {3, 7}, {4, 5}}, {{1, 8}, {2, 7}, {3, 4}, {5, 6}}, {{1, 8}, {2, 7}, {3, 5}, {4, 6}}, {{1, 8}, {2, 7}, {3, 6}, {4, 5}}}
• Sandbox Jul 12 at 16:36
• The number of pairs is A001147(n/2). Jul 12 at 17:18
• May we output the pairs "flat", for example 4 -> [[4,3,2,1],[4,2,3,1],[4,1,3,2]]? Jul 12 at 18:58
• @loopywalt No.឵ Jul 12 at 19:12

# Jelly, 9 bytes

Œ!HĊĠ€Ṣ€Q

Try it online!

Œ!           All permutations of [1 .. n].
H          Halve each number in each permutation
Ċ         rounding up,
Ġ€       group indices of equal values in each,
Ṣ€     sort each index-grouping,
Q    and uniquify.

# Curry (PAKCS), 44 bytes

f n=g[1..n]
g[]=[]
g(a:b++c:d)=(a,c):g(b++d)

Try it online!

This is a non-deterministic function whose return values are the all the ouputs.

# Python, 84 bytes

def f(n,o={}):(n>sum(1>o[K]!=f(n-1,o|{K:n})for K in o)==f(n-1,o|{n:0}))==n==print(o)

Attempt This Online!

### Previous Python, 91 bytes

def f(n,*o):[f(n-1,*{*o}^{(K,n),K})for K in o if-1*K][n-1:]or f(n-1,*o,n)if n else print(o)

Attempt This Online!

Takes n and prints all unique pairings.

How?

Counting down n either add the current value to an existing unfinished pair or start a new pair. One can check that this visits each pairing exactly once.

# Python, 10198 94 bytes

def f(r,*x):
if r:a,*r=r;[f({*r}-{b},*x,(a,b))for b in r]
else:print(x)
def g(n):f(range(n))

Attempt This Online!

Takes $$\n\$$ as input, operates on the set $$\[0,n)\$$, prints tuples of tuples.

-3 bytes from @Unrelated String by using splatting instead of passing in an array
-4 bytes from @pxeger by using list comprehension

• I realized my mistake immediately after posting :P
Jul 12 at 18:40
• Since you never mutate x (which is fortunate, else the function would violate the reusability requirement), 98 with some more splatting Jul 12 at 19:01
• 94 bytes by squishing the loop into a comprehension: ato.pxeger.com/… Jul 12 at 19:19
• Bonus: 79 bytes in Whython: ato.pxeger.com/… Jul 12 at 19:31

# VyxalR, 9 bytes

Ṗƛ2ẇvss;U

Try it Online!

Takes $$\n\$$ as input.

Ṗƛ2ẇvss;U
Ṗ         # Permutations of [1, n]
ƛ        # For each:
2ẇ      #  Split into chunks of length 2
vs    #  Sort each
s   #  Sort
;  # Close map
U # Uniquify

# Vyxal, 9 bytes

dɾ2ḋḋ'fÞu

Try it Online!

Port of caird's Jelly answer, takes $$\\frac{n}{2}\$$ as input.

dɾ2ḋḋ'fÞu
d         # Double, n × 2
ɾ        # Range [1, that]
2ḋ      # Combinations without replacement of length 2
ḋ     # Combinations without replacement of length {input}
'    # Filter for:
fÞu #  Is it unique after flattening?
• nooooo ninja'ed Jul 12 at 16:54
• Who is "caird"? Jul 13 at 18:39

# Wolfram Language (Mathematica), 52 bytes

Map[Union,{#~Partition~2&/@Permutations@Range@#},3]&

Try it online!

Input $$\n\$$. Returns a list of pair-lists, wrapped in a list.

Map[Union,{#~Partition~2&/@Permutations@Range@#},3]&
Permutations@Range@#     permutations
#~Partition~2&/@                           pair
{                                    }        increase depth by 1
Map[Union,                                      ,3]     unique all

Since Map does not apply at level 0 by default, wrapping the output with { } saves 2 bytes over including that level explicitly, e.g. with Map[Union,...,{0,2}] or u@Map[u=Union,...,2].

-1 if output wrapped in a Derivative[1] rather than a List is acceptable.

f n=g[1..n]
g[]=[[]]
g(h:t)=[(h,e):x|e<-t,x<-g$filter(e/=)t] Attempt This Online! Not sure if it can be improved. # 05AB1E, 10 bytes Lœε2ô€{{}ê Alternative with the same byte-count (thanks to @CommandMaster): L©.Ææʒ˜{®Q Explanation: L # Push a list in the range [1, (implicit) input] œ # Get all permutations of this list ε # Map over each permutation: 2ô # Split it into parts of size 2 €{ # Sort each inner pair { # Then sort all pairs }ê # After the map: sort and uniquify the list of lists of pairs # (which in this case is faster than just an uniquify) # (after which the result is output implicitly) L # Push a list in the range [1, (implicit) input] © # Store this list in variable ® (without popping) .Æ # Create all sorted unique pairs of this list æ # Get the powerset of this list of pairs ʒ # Filter each inner list of pairs by: ˜ # Flatten it to a single list { # Sort it ®Q # Check if it's equal to list [1,input] from variable ® # (after which the filtered list is output implicitly) • An alternative 10 bytes: L©.Ææʒ˜{®Q (or equivalently L.Ææʒ˜{ILQ) Jul 13 at 6:30 • @CommandMaster Thanks, added! I actually started out using 2.Æ initially, before I came with this 10-byter. I forgot the 2 was implicit for it, though. 😅 Jul 13 at 7:49 • æ is the powerset, not all permutations Jul 16 at 4:05 • @CommandMaster Woops, I know that, but I accidently made an error because of the explanation above it. Fixed now. Jul 16 at 11:46 # R, 95 92 bytes f=\(n,v=1:n,a={},+=list)if(n,sapply(seq(v)[-1],\(i,b=c(1,i))f(n-2,v[-b],c(+v[b],a))),+a) Attempt This Online! # Factor + math.combinatorics, 75 bytes [ iota [ natural-sort ] dup '[ 2 group _ map @ ] map-permutations members ] Try it online! Uses $$\[0..n)\$$ instead of $$\[1..n]\$$ to save a byte. This would be more clearly written as [ iota [ 2 group [ natural-sort ] map natural-sort ] map-permutations members ] However, natural-sort is so long it's shorter to stick in a quotation, dup it, and fry them into the map-permutations quotation appropriately. I'll explain the second version since the first version constructs it. • iota Get an integer range from 0 inclusive to the input exclusive. • [ ... ] map-permutations Apply [ ... ] to each permutation of the above range and collect the results in a new sequence. • 2 group Group a sequence into pairs. e.g. { 1 2 3 4 } -> { { 1 2 } { 3 4 } }. • [ natural-sort ] map Sort each pair. • natural-sort Sort the sequence of pairs. • members Take the unique elements of a sequence. # Jelly, 10 bytes ŒcœcHFQƑ$Ƈ

Try it online!

## How it works

ŒcœcHFQƑ$Ƈ - Main link. Takes n on the left Œc - Unordered pairs H - Halve œc - Combinations without replacement of length n/2$Ƈ - Keep those for which the following is true:
F     -   When flattened,
Ƒ   -   the list is unchanged after
Q    -   deduplication

# Husk, 10 bytes

umȯOmOC2Pḣ

Try it online!

Range () => permutations (P) => map (m) 3 functions (ȯ) over each: cut into sublists of 2 (C2), sort each sublist (mO), and sort each (O) => finally keep only unique elements (u).

# Python, 124 bytes

Thanks to user Steffan for -4 bytes.

Takes the integer $$\ \frac n 2 \$$ as input and operates on the set $$\ [0, n) \$$. Outputs a set of tuples of tuples.

lambda n:{t for t in c(sorted(c(range(2*n),2)),n)if len(sum(t,()))==len({*sum(t,())})}
from itertools import*;c=combinations

Attempt This Online!

# SageMath, 35 bytes

lambda n:PerfectMatchings(n).list()

Try it on SageMathCell!

# Rust, 225 bytes

My other attempts where even longer. So much collect().collect()..

fn f(e:u8)->Vec<Vec<(u8,u8)>>{let g=|t,e|if t+1<e{t+1}else{t+2};if e==0{vec![vec![]]}else{(1..e).flat_map(|q|f(e-2).iter().map(|o|o.iter().map(|m|(g(m.0,q),g(m.1,q))).chain([(0,q)]).collect()).collect::<Vec<_>>()).collect()}}
• Probably you can change if t+1<e{t+1}else{t+2} to t+2-(t+1<e)as _? Jul 14 at 23:56

# Rust, 191 186 bytes

fn f(e:u8)->Vec<Vec<[u8;2]>>{if e>0{(1..e).flat_map(|q|{let mut k=f(e-2);for r in&mut k{for m in r.iter_mut(){for n in m{*n+=(*n>=q)as u8}}r.push([q,e])}k}).collect()}else{vec![vec![]]}}

Attempt This Online!

A golfed version of mousetail's solution.

-5 bytes thanks to alephalpha. Didn't realize that r.iter_mut() can save a separate for r in &mut k.

List of changes:

• I decided to remove .collect::<Vec<_>>() right inside flat_map in favor of taking an owned Vec (that is returned from f(e-2)) and modifying it.
• Then, since both fields of (u8,u8) are being modified using the same formula, I decided to change its type to [u8;2] and iterate over it instead.
• Finally, switching to 1-based solution saved a few bytes related to arithmetic.
• -5 bytes: fn f(e:u8)->Vec<Vec<[u8;2]>>{if e>0{(1..e).flat_map(|q|{let mut k=f(e-2);for r in&mut k{for m in r.iter_mut(){for n in m{*n+=(*n>=q)as u8}}r.push([q,e])}k}).collect()}else{vec![vec![]]}} Jul 15 at 1:57
• -2 bytes: for m in r.iter_mut(){for n in m{...}} => for n in r.iter_mut().flatten(){...} Jul 15 at 3:00

# lin, 52 bytes

.\n $.n t2comb.n2/ comb \; # flat dup uniq = Try it here! Returns an iterator with 0-indexed results. For testing purposes (use -i flag if running locally): 6 ; _ wrap_ .\n$.n t2comb.n2/ comb \; #
flat dup uniq =

## Explanation

Assuming even integer input n (.\n).

• \$ .n t push range [0..n)
• 2comb length-2 combinations
• .n2/ comb length-(n/2) combinations
• \; # filter...
• flat dup uniq = check if element flattened is unique

# JavaScript (V8), 112 bytes

Prints space-separated lists of comma-separated 0-indexed values.

f=(n,i=0,m,o,g=j=>++j<n?g(j,m&(q=1<<i|1<<j)||f(n,i,m|q,[o]+[i,j]+' ')):f(n,i+1,m,o))=>2**n+~m?i<n&&g(i):print(o)

Try it online!

# Pyth, 12 11 bytes

{mSSMcd2.PS

Try it online!

{mSSMcd2.PS
S  Range from 1 to the input
.P   Permutations
m           For each permutation:
cd2      - Chop into chunks of size 2
SM         - Sort each chunk
S           - Sort the list of chunks
{            Deduplicate

# Jelly, 10 bytes

Œ!s2Ṣ€ṢƊ€Q

Attempt This Online!

Now that it's been beaten, I'll post my own answer (also previously shared in chat).

Explanation:

Œ!            permutations of (implicit range from 1 to) n
Ɗ€     for each permutation:
s2            split into chunks of 2
Ṣ€          sort each pair
Ṣ         sort the list of pairs
Q    remove duplicates

# Ruby, 68 bytes

->n{[*1..n].permutation.map{|c|c.each_slice(2).map(&:sort).sort}|[]}

Try it online!

# Charcoal, 59 bytes

Ｎθ⊞υ⟦⟧Ｆ⊗θ«≔⟦⟧ηＦυ«Ｆ⌕ＡＥκＬλ¹⊞ηＥκ⎇⁻λνμ⁺μ⟦ι⟧¿‹Ｌκθ⊞η⊞Ｏκ⟦ι⟧»≔ηυ»Ｉη

Try it online! Link is to verbose version of code. Takes ⁿ⁄2 as input. Explanation:

Ｎθ

Input ⁿ⁄2.

⊞υ⟦⟧

Ｆ⊗θ«

Loop from 0 to n.

≔⟦⟧η

Start collecting pairings

Ｆυ«

Loop over the existing pairings.

Ｆ⌕ＡＥκＬλ¹

Loop over the unpaired numbers in this pairing.

⊞ηＥκ⎇⁻λνμ⁺μ⟦ι⟧

Pair the current number with that unpaired number.

¿‹Ｌκθ⊞η⊞Ｏκ⟦ι⟧

If there is room then also add the number as an unpaired number.

»≔ηυ

Save the resulting pairings.

»Ｉη

Output the final pairings.

# JavaScript (Node.js), 114 bytes

f=(n,[i,...a]=[...Array(n)].map((_,i)=>i+1))=>i?a.flatMap(j=>f(n,a.filter(k=>k-i&&k-j)).map(r=>[[i,j],...r])):[[]]

Attempt This Online!