Every possible pairing

Question

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 code-golf, 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}}}

Answer 1

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.

Answer 2

Vyxal R, 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?

Answer 3

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.

Answer 4

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!

Using dictionaries instead of sets.

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.

Answer 5

Python, 101 98 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

Answer 6

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.

Answer 7

Haskell, 60 bytes

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.

Answer 8

05AB1E, 10 bytes

Lœε2ô€{{}ê

Try it online or verify all test cases.

Alternative with the same byte-count (thanks to @CommandMaster):

L©.Ææʒ˜{®Q

Try it online or verify all test cases.

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)

Answer 9

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!

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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!

Answer 14

Ruby, 68 bytes

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

Try it online!

Answer 15

SageMath, 35 bytes

lambda n:PerfectMatchings(n).list()

Try it on SageMathCell!

Answer 16

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()}}

Answer 17

Rust, ¹⁹¹ 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.

Answer 18

lin, 52 bytes

.\n $`.n `t2`comb.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 `t2`comb.n2/ `comb \; `#
`flat dup `uniq `=

Explanation

Assuming even integer input n (.\n).

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

Answer 19

Pip, 20 bytes

UQ(SNSN*_CHa/2MPM,a)

Try It Online!

Operating on the range \$[0,n)\$ instead of \$[1,n]\$.

I'm just porting some of the other answers here like the Jelly and Vyxal one, so hopefully it is right.

Answer 20

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!

Answer 21

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

Answer 22

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     

Answer 23

Charcoal, 59 bytes

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

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

Ｎθ

Input ⁿ⁄2.

⊞υ⟦⟧

Start with a pairing of no numbers.

Ｆ⊗θ«

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.

Answer 24

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!