How to rearrange array using Python?

Thomas 'PointedEars' Lahn PointedEars at web.de
Fri Jul 31 04:29:47 CEST 2015


Mark Lawrence wrote:

> On 30/07/2015 21:31, Martin Schöön wrote:
>> I am just back from visiting my sisters and the younger of them
>> was busy planning a youth orchestra summer camp. For some reason
>> the kids are allowed to wish with whom they want to share rooms
>> and my sister spent several evenings placing kids in rooms
>> according to these wishes. It struck me that at least some of this
>> work could be done by silicon running code.
>> […]
>> An added piece of information is the number of and sizes
>> of rooms. I want to overlay this on the array and re-shuffle
>> until as many of the wishes as possible are fulfilled.
>> […]
>> How do I go about doing that?
>>
>> Note: This example is worse than the real life problem as
>> most kids go to this camp with friends and wishes are
>> highly coordinated. I used a random number generator to
>> create wishes... The real problem involves some 80 kids.
>> There are some more differences but let us leave them out
>> for now.
> 
> I'm not absolutely certain but I think you're into what's known as a
> constraint satisfaction problem, in which case this
> https://pypi.python.org/pypi/python-constraint/1.2 is as good a starting
> point as any.  If I'm wrong we'll soon get told :)

It is a CSP indeed, and as I was reading the OP I was thinking of SWI-
Prolog, not Python, for the solution.  Using a PRNG and simple reshuffling 
cannot be the correct approach because you cannot be sure that you do not 
get the same number twice, the same solution twice, and that you can solve 
the problem in finite time.  The correct approach, *a* correct approach at 
least, is as you would do without computers: keeping track of the solutions, 
backtracking, and discarding the solutions that were worse than the so-far-
best one.

However, fascinating to learn that Python has something to offer for CSPs, 
too.

Please trim your quotes to the relevant minimum.

-- 
PointedEars

Twitter: @PointedEars2
Please do not cc me. / Bitte keine Kopien per E-Mail.


More information about the Python-list mailing list