osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Partitioning a list


On Wed, 22 Aug 2018 at 00:44, Poul Riis <priisdk at 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