Group a range of integers such as no pair of numbers is shared by two or more groups This is a duplicate of another question from StackOverflow. I've been advised to post it on Mathematics by another user who clearly has more experience in combinatorics than myself, and, although I have my doubts, I hope he is right.

You are given two numbers, $N$ and $G$. The goal is to create an algorithm to split a range of integers $[1-N]$ in equal groups of $G$ numbers each, in reasonable time. Each pair of numbers must be placed in exactly one group. Order does not matter.

For example, given $N=9$ and $G=3$, I could get these 12 groups:
1-2-3
1-4-5
1-6-7
1-8-9
2-4-6
2-5-8
2-7-9
3-4-9
3-5-7
3-6-8
4-7-8
5-6-9

As you can see, each possible pair of numbers from 1 to 9 is found in exactly one group. I should also mention that such grouping cannot be done for every possible combination of $N$ and $G$.

Talking about pairs of numbers makes me naturally think of edges in graphs. Each pairing can be represented by an edge of the graph. Since we want all possible pairings (without repeats), we're looking at the desired state of a complete graph on $N$ vertices, $K_N$. Each group is a complete subgraph of $G$ vertices. that produces pairs in accordance with the edges The problem can be regarded as finding a decomposition of $K_N$ into copies of $K_G$ - a set of edge-disjoint subgraphs that account for all the edges in $K_N$.
There are $N(N-1)/2$ edges in $K_N$, and $N-1$ edges from each vertex, and similiarly there are $G(G-1)/2$ edges in $K_G$, and $G-1$ edges from each vertex. So as a minimum consideration we need:
$$\begin{align} G-1 &\mid N-1 \tag{1} \\
G(G-1)/2 &\mid N(N-1)/2 \tag{2}
\end{align}$$


*

*the first so that the $k=(N-1)/(G-1)$ groups involving any one element exhaust the edges from (pairs with) that element and

*the second to ensure that that the groups can exhaust all pairings exactly.


For example, with $G=3$, $N$ must be odd and either $N$ or $N-1$ must be divisible by $3$ (to satisfy the second condition). So, for example, $N=5, G=3$ is not possible. For $G=4
However for $(N,G) = (7,3)$, we have $2 \mid 6$ and $3 \mid 21$, so those criteria are met and the $K_7$ graph decomposes into $7$ $K_3$ graphs:

Numbering the vertices from $1$ at the top clockwise, this corresponds to groups  $\{1,2,6\},\{1,3,7\},\{1,4,5\},\{2,3,4\},\{2,5,7\},\{3,5,6\},\{4,6,7\}$
For $G=4$, the smallest $N$ for which divisibility is met is $13$, and that works as follows:
$\{1,2,3,4\}$
$\{1,5,6,7\}$
$\{1,8,9,10\}$
$\{1,11,12,13\}$
$\{2,5,8,11\}$
$\{2,6,9,12\}$
$\{2,7,10,13\}$
$\{3,5,9,13\}$
$\{3,6,10,11\}$
$\{3,7,8,12\}$
$\{4,5,10,12\}$
$\{4,6,8,13\}$
$\{4,7,9,11\}$
My expectation is that whenever the divisibility criteria are met, it will be relatively simple to generate the required sets just by tracking which pairings have been used.
