Let's first describe a notation for our partitions. Let $p_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p_i$ as  $$p_i=b_{i,1},b_{i,2},...b_{i,S/2}$$

In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p_i$, each pair in $p_i$ must be sorted. The pairs must also be sorted among themselves i.e.

$$b_{i,j}[0] < b_{i,j}[1]  \;\;\text{and} \;\; b_{i,j} < b_{i,j+1} \;\;\forall j$$

The ordering of the partitions is then defined similarly to other lexicographic orderings.

$$p_i > p_{k} \iff \exists j \;\; \text{s.t.}\;\; \forall j'\in[1, j) \;\;  b_{i,j}=b_{k,j} \land  b_{i,j'}>b_{k,j'}$$


Now, given some partition $p_i$, we can return the next lexicographically larger partition $p_{i+1}$ by using logic similar to [the algorithm for obtaining the next permutation of a set of elements][1]. Let us first describe a function $swap(p_i, j)$ and $sort(p_i, j)$.

- $swap(p_i, j) \rightarrow \;\;$ Find the largest $j$ such that $\exists x\in b_{i,j'}$ such that $x > b_{i,j}[1]$ for some $j'> j$. Then swap $b_{i,j}[1]$ and $x$.

- $sort(p_i, j) \rightarrow \;\;$ Sort all of the elements from $b_{i,j}[0]$ to $b_{i,S/2}[1]$ i.e. after calling $sort(p_i, j)$, the sequence $b_{i,j}[0], b_{i,j}[1], ..., b_{i,S/2}[0],b_{i,S/2}[1]$ should be non-decreasing.

Now, we claim that given a partition $p_i$, we can obtain $p_{i+1}$ by running $swap(p_i, S/2 - 1)$ followed by $sort(p_i, S/2)$. The reasoning is identical to that of the "next permutation algorithm" - We must find the largest $j$ such that we can swap $b_{i,j}[1]$ with the next largest value while not changing anything in $b_{i,j'}$ for $j' < j$. After the swap, we must sort the remaining elements to ensure that it is the smallest increase possible. If the remaining elements were not sorted, then by sorting them we would obtain a partition greater than $p_i$ but less than $p_{i+1}$, which is a contradiction. 


  [1]: https://leetcode.com/articles/next-permutation/