On Thu, 23 Aug 2018 at 15:32, Sibylle Koczian <nulla.epist...@web.de> wrote: > > Am 21.08.2018 um 23:36 schrieb Poul Riis: > > I would like to list all possible ways to put N students in groups of k > > students (suppose that k divides N) with the restriction that no two > > students should ever meet each other in more than one group. > > I think this is a classical problem and I think there must be a python > > solution out there but I cannot find it. For instance, numpy's array_split > > only lists one (trivial) split. > > I would be happy if someone could refer me to a general python algorithm > > solving the problem. > > > This is indeed a classic (or rather the generalization of a classic): > Kirkman's Schoolgirl Problem (for N = 15), first published 1850.
I think the general concept is called a Steiner system: https://en.wikipedia.org/wiki/Steiner_system In the notation of that article you would like to describe S(2, k, N). The article says: It can be shown that if there is a Steiner system S(2, k, N), where k is a prime power greater than 1, then N = 1 or k (mod k(k−1)) which may be relevant for what you are doing. For the case k=3 you can find more information by searching for Steiner Triple Systems. I don't know how to construct Steiner systems but without thinking very hard about it I imagine that you can build larger Steiner systems from smaller ones in some way. Once you have a Steiner system you can then consider all the permutations of mapping your students onto the elements of the system - there will be N! of those but possibly with a k! duplication so maybe there's an efficient way to only enumerate the N!/k! possibilities. Hopefully N isn't too large... -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
