# Algorithm to arrange N people into groups of K

• MHB
• Theia
In summary, the problem at hand is to find a reasonable solution for N people meeting in groups of K people without anyone meeting more than once. This requires N to be divisible by K and N-1 to be divisible by K-1. Two approaches that can be used to solve this problem are brute-force and graph theory solutions. The most straightforward solution is to try all possible combinations of the N people in groups of K and check for any repeated meetings, but this can be computationally expensive. The other approach involves modeling the problem as an undirected graph and finding a minimum vertex cover of size K. This can be done using various well-studied algorithms. The conversation also mentions the use of "disjoint Steiner system" or

#### Theia

Hi all!

I've been trying to find a reasonable way to solve following problem:

N people meet each others in groups of K people such that no one meets more than once.

If I'm not mistaken, this requires two things:
• N must be divisible by K
• N - 1 must be divisible by K - 1.
Let's assume these conditions hold. How to proceed...? (Wondering) For a more concrete example one can use for example N = 15 and K = 3.

The most straightforward solution is to use a brute-force approach. This means that you can try all possible combinations of the N people in groups of K people and check if no one has met more than once. This may be computationally expensive and is not always feasible.Another approach is to use a graph theory solution. You can model the problem as an undirected graph with N nodes, where each node represents a person. Then, you can connect two nodes if the two people have already met. You want to find a way to divide the graph into K connected subgraphs such that each subgraph has N/K nodes. This can be done by finding a minimum vertex cover of size K in the graph. A vertex cover is a set of nodes such that every edge in the graph is incident to at least one node in the set. Finding a minimum vertex cover is a well-studied problem and there are several algorithms to solve it. Hope this helps!

There appears to be different approaches that one can find using keyword "disjoint Steiner system" or "disjoint Kirkman system". The case N = 15, K = 3 is the famous Kirkman's schoolgirl problem.

It still took me some years to find time and suitable algorithm for this... The code below gives one solution to the problem I described in opening post - at least in the case N = 15 and K = 3

Fortran:
program zenz
implicit none
integer, parameter :: N = 15, K = 3
integer :: i, imax, j, jmax, v
integer, allocatable :: groups(:,:), joukko(:,:)
integer, allocatable :: valitsin(:), valitut(:), tb_valitsin(:)
logical :: tavattu(N,N) = .false.
!valitsin = generoi ryhmät taulukkoon groups
!groups = lista ryhmistä, jotka on mahdollista muodostaa
!valitut = lista ryhmien indekseistä taulukossa groups, mitkä on valittu tapaamisiin
!tavattu = true jos henkilöt i ja j ovat tavanneet
!table = listaa kierroksen ryhmät
!tb_valitsin = permutoi valitut ryhmät niin, että tapaamiset onnistuu
intrinsic sum, ubound, mod

allocate(groups(1:binomial(N,K),K))
allocate(valitut(1:N*(N-1)/(K*(K-1))))

!alustetaan tavattu-taulukko, sillä kukin henkilö on tavannut itsensä.
do i = 1,N
tavattu(i,i) = .true.
end do

allocate(valitsin(1:N))
valitsin = 0
valitsin(N-K+1:N) = 1

i = 1
do while(sum(valitsin) > 0)
groups(i,:) = collect(valitsin)
valitsin = lex(valitsin)
i = i + 1
end do

!sitten on koostettava listasta groups mukaan otetut ryhmät taulukkoon valitut

valitut = 0
i = 0 !edellinen täytetty paikka valitut-taulukossa
j = 0 !edellinen valittu ryhmä taulukosta groups
imax = ubound(valitut,1) !ryhmiä ei voi olla valittuna tätä enempää
jmax = ubound(groups,1) !ryhmien lukumäärä

do while(.not. all_met(tavattu))
j = j + 1 !seuraava ryhmä, jota kokeillaan lisätä
!jos ryhmät jo loppui
if(j > jmax) then
!otetaan uudeksi j:ksi edellinen lisätty ryhmä
j = valitut(i)
!valitut(i) = 0
i = i - 1
!poistetaan tämän indeksin kuvaamat tapaamiset
tavattu = rem_gr(j,tavattu)
cycle
end if
!jos ryhmä voidaan lisätä
tavattu = add_gr(j,tavattu) !lisätään ryhmän tapaamiset
i = i + 1
valitut(i) = j
!write(*,*) ''
!write(*,*) valitut
!write(*,*) ''
!do v = 1,N
!  write(*,*) tavattu(v,:)
!end do
cycle
end if
end do

write(*,*) 'Ratkaisu löytynyt!'

!sitten täytyy koostaa kierrosten tapaamiset perustuen valitut-taulukon ryhmiin. yksi henkilö voi olla vain yhdessä tapaamisessa kullakin kierroksella.

v = ubound(valitut,1)

!yhdellä kierroksella on N/K ryhmää. alustetaan tb_valitsin
tb_valitsin = init(v,N/K)

!kootaan valitut ryhmät taulukkoon joukko
allocate(joukko(1:v,1:K))
do i = 1,v
joukko(i,:) = groups(valitut(i),:)
end do

i = 1
do
!tarkistetaan, onko nykyinen permutaatio sopiva
if(sopiva(tb_valitsin,joukko)) then
!jos on, niin tulostetaan tulos...
write(*,*) i
do j = 1, ubound(tb_valitsin,1)
if(tb_valitsin(j) > 0) write(*,*) joukko(j,:)
end do
write(*,*) ''
i = i + 1
!...ja poistetaan löydetty tulos listoista.
call refresh(tb_valitsin,joukko)
if(ubound(tb_valitsin,1) == N/K) then
write(*,*) i
do j = 1,N/K
write(*,*) joukko(j,:)
end do
exit
end if
end if
!ellei, niin tutkitaan seuraava permutaatio
tb_valitsin = lex(tb_valitsin)
end do

contains

subroutine refresh(cho, grs)
implicit none
integer, allocatable, intent(inout) :: cho(:), grs(:,:)
integer, allocatable :: gros(:,:)
integer :: iii, ub, jjj
intrinsic ubound
ub = ubound(cho,1)
jjj = 1
allocate(gros(1:ub-N/K,1:K))
do iii = 1,ub
if(cho(iii) == 0) then
gros(jjj,:) = grs(iii,:)
jjj = jjj + 1
end if
end do
deallocate(grs)
grs = gros
cho = init(ub-N/K,N/K)
end subroutine refresh

function sopiva(cho,grs) result(joovai)
implicit none
!tutkii, onko valitsimen cho osoittama ryhmäkokoelma grs:stä sopiva tapaamiskierrokseksi
integer, allocatable, intent(in) :: cho(:), grs(:,:)
logical :: joovai, rivi(1:N)
integer :: iii, jjj
intrinsic ubound
rivi = .false.
do iii = 1, ubound(cho,1)
if(cho(iii) > 0) then
do jjj = 1,K
rivi(grs(iii,jjj)) = .true.
end do
end if
end do
joovai = all(rivi)
end function sopiva

function init(pit,lkm) result(lista)
implicit none
!alustaa valitsimen, pituus pit niin, että lopussa on lkm verran ykkösiä. loput nollia.
integer, intent(in) :: pit, lkm
integer, allocatable :: lista(:)
allocate(lista(1:pit))
lista = 0
lista(pit-lkm+1:pit) = 1
end function init

implicit none
!tutkii, voiko ryhmän numero nro tapaamiset lisätä tapaamistaulukkoon ref
integer, intent(in) :: nro
logical, intent(in) :: ref(N,N)
integer :: gta(1:K), ii, jj
logical :: r
gta = groups(nro,:) !group to add
r = .false. !eli ei voi lisätä
do ii = 1,K-1
do jj = ii+1,K
if(ref(gta(ii),gta(jj)) .eqv. .true.) return
if(ref(gta(jj),gta(ii)) .eqv. .true.) return
end do
end do
r = .true.

implicit none
!lisää ryhmän numero nro tapaamiset tapaamistaulukkoon ref
integer, intent(in) :: nro
logical, intent(in) :: ref(N,N)
integer :: gta(1:K), ii, jj
logical :: new_ref(N,N)
gta = groups(nro,:) !group to add
new_ref = ref
do ii = 1,K-1
do jj = ii+1,K
new_ref(gta(ii),gta(jj)) = .true.
new_ref(gta(jj),gta(ii)) = .true.
end do
end do

function rem_gr(nro,ref) result(new_ref)
implicit none
!poistaa ryhmän numero nro tapaamiset tapaamistaulukosta ref
integer, intent(in) :: nro
logical, intent(in) :: ref(N,N)
integer :: gta(1:K), ii, jj
logical :: new_ref(N,N)
gta = groups(nro,:) !group to remove
new_ref = ref
do ii = 1,K-1
do jj = ii+1,K
new_ref(gta(ii),gta(jj)) = .false.
new_ref(gta(jj),gta(ii)) = .false.
end do
end do
end function rem_gr

function all_met(ref) result(r)
implicit none
logical, intent(in) :: ref(N,N)
integer :: am, ii
logical :: r
intrinsic all
am = 0
r = .false.
do ii = 1,N
if(all(ref(ii,:))) am = am + 1
end do
if(am == N) r = .true.
end function all_met

function collect(t) result(g)
implicit none
!muodostaa ryhmäkandidaatit osanottajalistasta valitsimen t avulla.
integer, intent(in) :: t(N)
integer :: g(K), i, j
j = 1
do i = 1,N
if(t(i) > 0) then
g(j) = i
j = j + 1
if(j > K) return
end if
end do
end function collect

recursive function binomial(n,k) result(b)
implicit none
integer, intent(in) :: n, k
integer :: b
if(k > n) then
b = 0
return
end if
if((k == 0) .or. (k == n) ) then
b = 1
return
end if
b = binomial(n - 1, k - 1) + binomial(n - 1,k)
end function binomial
!
function lex(taul) result(ntaul)
implicit none
integer, allocatable, intent(in) :: taul(:)
integer, allocatable :: ntaul(:), t(:)
integer :: k, m, apu
t = taul
ntaul = t
k = find_k(taul)
if(k == -1) then
ntaul = 0
return
end if
m = find_m(taul,k)

apu = t(k)
t(k) = t(m)
t(m) = apu

ntaul = reverse(t,k)
end function lex
!
function reverse(taul,k) result(t)
implicit none
integer, allocatable, intent(in) :: taul(:)
integer, intent(in) :: k
integer :: a, b, apu, z
integer, allocatable :: t(:), alku(:), loppu(:)
intrinsic ubound
z = ubound(taul,1)
allocate(alku(z),loppu(z),t(z))
alku = 0
loppu = 0
alku(1:k) = taul(1:k)
loppu(k+1:z) = taul(k+1:z)
a = k + 1
b = z
do
apu = loppu(a)
loppu(a) = loppu(b)
loppu(b) = apu
a = a + 1
b = b - 1
if(a >= b) exit
end do
t = alku + loppu
end function reverse
!
function find_m(taul,k) result(m)
implicit none
integer, intent(in) :: k
integer, allocatable, intent(in) :: taul(:)
integer :: m, z
intrinsic ubound
z = ubound(taul,1)
m = z
do
if(taul(k) < taul(m)) return
m = m - 1
if(m == k) exit
end do
m = -1
end function find_m
!
function find_k(taul) result(k)
implicit none
integer, allocatable, intent(in) :: taul(:)
integer :: k, z
intrinsic ubound
z = ubound(taul,1)
do k = z - 1, 1, -1
if(taul(k) < taul(k + 1)) return
end do
k = -1
end function find_k
!
end program zenz

Theia said:
It still took me some years to find time and suitable algorithm for this...
That's a shame. If MHB had been part of PF in 2021 you might have been pointed towards this: https://cs.lmu.edu/~ray/notes/kirkman/.

Theia said:
Hi all!

I've been trying to find a reasonable way to solve following problem:

N people meet each others in groups of K people such that no one meets more than once.

If I'm not mistaken, this requires two things:
• N must be divisible by K
• N - 1 must be divisible by K - 1.
Let's assume these conditions hold. How to proceed...? (Wondering) For a more concrete example one can use for example N = 15 and K = 3.
Why is this not a solution for ##N =3, K =2##?

A meets B, A meets C, B meets C?

PeroK said:
Why is this not a solution for ##N =3, K =2##?

A meets B, A meets C, B meets C?
In each round, all people must be in exactly one meeting. This approach puts either all people into two meetings at the same time, or leaves one person without a meeting. Thus it's not considered as a solution this time.

Theia said:
In each round, all people must be in exactly one meeting.
But you didn't specify that - you didn't even mention rounds!

Kirkman's Schoolgirl Problem and its generalizations are well documented (e.g. https://en.wikipedia.org/wiki/Kirkman's_schoolgirl_problem), if you have a question relating to a specific problem it would probably be best to refer to or quote an existing definition in full.

PeroK

## 1. How does the algorithm work?

The algorithm works by first dividing the total number of people (N) by the desired group size (K) to determine the total number of groups (G). Then, it assigns the first K people to the first group, the next K people to the second group, and so on, until all N people have been assigned to G groups. If there are any remaining people, they will be evenly distributed among the existing groups.

## 2. Can the algorithm handle different group sizes?

Yes, the algorithm can handle different group sizes. As long as the total number of people (N) is divisible by the desired group size (K), the algorithm will work. If the group size does not evenly divide N, then the remaining people will be evenly distributed among the existing groups.

## 3. How efficient is the algorithm?

The efficiency of the algorithm depends on the programming language and implementation used. In general, it has a time complexity of O(N) as it needs to loop through each person and assign them to a group. However, there may be more efficient ways to implement the algorithm in certain programming languages.

## 4. Can the algorithm account for certain constraints or preferences?

Yes, the algorithm can be modified to account for certain constraints or preferences. For example, if there are certain people who should not be in the same group, the algorithm can be adjusted to ensure they are not assigned to the same group. It can also be modified to prioritize certain group sizes or to evenly distribute people with specific characteristics among the groups.

## 5. Are there any limitations to the algorithm?

One limitation of this algorithm is that it may not work if the total number of people (N) is not divisible by the desired group size (K). In such cases, the algorithm may need to be adjusted or an alternative approach may need to be used. Additionally, the algorithm may not be suitable for very large numbers of people as it may become less efficient.