> On Aug 22, 2018, at 8:51 AM, Paul Moore <p.f.mo...@gmail.com> wrote: > >> On Wed, 22 Aug 2018 at 00:44, Poul Riis <prii...@gmail.com> wrote: >> >> 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. > > The basic problem seems to be a simple case of looking for > combinations of k items from N, which is something itertools can help > you with. I don't understand the restriction (or at least, if I > understand the basic requirement then the restriction makes no sense > to me, as a set of combinations only puts any one student in one > group, so "meeting someone in more than one group" isn't possible). > But what I'd be inclined to do, at least as a first approach (refine > it if it's too slow for your real case) is to take each basic > solution, and check if it satisfies the extra constraint - keep the > ones that do. > > Combinatorial problems typically grow very fast as N (and/or k) > increase, so that approach may not work as a practical solution, but > it will at least mean that you code your requirement in an executable > form (which you can test for small numbers) and then you'll have a > more precise problem to describe when looking for help tuning it. > > Paul > Paul, my understanding of the problem is that you want to create multiple divisions of the larger group into smaller groups, such that if two people are in the same group in 1 division, they never appear together in other divisions.
One sample problem which I have had to solve with a similar restriction (but in my case was to minimize not eliminate repeats) was scheduling races. Say you have 9 cars you want to race in triples, and no pair of cars should ever meet twice. One option would be the following matches: 1,2,3; 4,5,6; 7,8,9 1,4,7; 2,5,8; 3,6,9 1,5,9; 2,6,7; 3,4,8 1,6,8; 2,4,9; 3,5,7 You can show this is the most number of triples you can get out of 9, as every number has been paired with every other number once, so to create another triple, you must get a duplicate pairing. I don’t know of any general algorithm to generate these. -- https://mail.python.org/mailman/listinfo/python-list
