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, NN and GG. The goal is to create an algorithm to split a range of integers [1−N][1-N] in equal groups of GG numbers each, in reasonable time. Each pair of numbers must be placed in exactly one group. Order does not matter.

For example, given N=9N=9 and G=3G=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 NN and GG.

=================

  

 

What do you mean when you say that such grouping cannot be done for every possible combination of N and G?
– Thanassis
2 days ago

  

 

@Thanassis, aside from obvious N≥G condition – consider N=4 and G=3, for example. There is no way one can split numbers [1, 2, 3, 4] into groups of 3 such that each pair of numbers is covered. This set is even small enough to try to cover all possible combinations manually.
– DeFazer
2 days ago

  

 

What you are describing is called a block design and has been studied pretty extensively. Specifically, you want an (N,G,1)(N,G,1)-design. I suspect there are algorithms out there for generating them, as well as criteria for when they exist in the first place.
– Greg Martin
2 days ago

1

 

Talking about pairs of numbers makes me naturally think of edges in graphs. The problem can be regarded as finding a decomposition of KNK_N into copies of KGK_G.
– Joffan
2 days ago

  

 

Although not stated, we can assume that N≥GN\ge G.I was confused a bit with the wording of the problem but it is clear to me now. Given the description of the problem N=kGN = kG, with kk being a positive integer. You can state this, instead of making the loose statement that not all combinations of NN and GG work.
– Thanassis
2 days ago

=================

1 Answer
1

=================

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 NN vertices, KNK_N. Each group is a complete subgraph of GG vertices. that produces pairs in accordance with the edges The problem can be regarded as finding a decomposition of KNK_N into copies of KGK_G – a set of edge-disjoint subgraphs that account for all the edges in KNK_N.

There are N(N−1)/2N(N-1)/2 edges in KNK_N, and N−1N-1 edges from each vertex, and similiarly there are G(G−1)/2G(G-1)/2 edges in KGK_G, and G−1G-1 edges from each vertex. So as a minimum consideration we need:
G−1∣N−1G(G−1)/2∣N(N−1)/2\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)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=3G=3, NN must be odd and either NN or N−1N-1 must be divisible by 33 (to satisfy the second condition). So, for example, N=5,G=3N=5, G=3 is not possible. For $G=4

However for (N,G)=(7,3)(N,G) = (7,3), we have 2∣62 \mid 6 and 3∣213 \mid 21, so those criteria are met and the K7K_7 graph decomposes into 77 K3K_3 graphs:

Numbering the vertices from 11 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}\{1,2,6\},\{1,3,7\},\{1,4,5\},\{2,3,4\},\{2,5,7\},\{3,5,6\},\{4,6,7\}

For G=4G=4, the smallest NN for which divisibility is met is 1313, and that works as follows:

{1,2,3,4}\{1,2,3,4\}
{1,5,6,7}\{1,5,6,7\}
{1,8,9,10}\{1,8,9,10\}
{1,11,12,13}\{1,11,12,13\}
{2,5,8,11}\{2,5,8,11\}
{2,6,9,12}\{2,6,9,12\}
{2,7,10,13}\{2,7,10,13\}
{3,5,9,13}\{3,5,9,13\}
{3,6,10,11}\{3,6,10,11\}
{3,7,8,12}\{3,7,8,12\}
{4,5,10,12}\{4,5,10,12\}
{4,6,8,13}\{4,6,8,13\}
{4,7,9,11}\{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.

  

 

Thanks! That’s very insightful. I’ve been able to modify my code a bit so it would definitely determine which NN and GG are guaranteed to yield results. Unfortunately, it’s exactly generating these sets that I have most trouble with: it goes perfect until I have 1 or 2 groups left, and then no possible groupings left. So I have to backtrack and try slightly different groupings, and try again, and try again… And this approach gives right results eventually, but it is very, very slow. Is it possible to if not predict these sets exactly, then at least somehow narrow the search?
– DeFazer
yesterday

  

 

@DeFazer What sort of NN and GG values are you working with? It might help me to work out your allocation issues. And you can click the checkmark next to my answer if you feel it has helped suitably 🙂
– Joffan
yesterday

  

 

to be honest, I’m not sure. Right now I’m just trying to determine possible algorithm efficiency and which values of NN and GG it can be expected to work with in reasonable time. But estimatively, I expect NN to be around 40 and GG to be around 6-10, although this is highly probable to change.
– DeFazer
yesterday

  

 

Sorry, but I can’t accept your answer (yet), because at the moment it doesn’t address the main issue – the time-efficient way to find such sets. I’ve already modelled this problem with graphs and even wrote some working code (you can actually examine it in the SO duplicate of the question – I didn’t repost it here because I thought that it won’t be relevant to the mathematical side of problem), but the brute-force backtracking approach is very slow.
– DeFazer
yesterday