Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Mark Lawrence <breamoreboy@yahoo.co.uk>
Subject: Re: How to rearrange array using Python?
Date: Thu, 30 Jul 2015 23:21:03 +0100
References: <d1vftgF65svU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.1.0
In-Reply-To: <d1vftgF65svU1@mid.individual.net>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1100.1438294883.3674.python-list@python.org>
Lines: 69
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:94792

On 30/07/2015 21:31, Martin Schöön wrote:
> Here is a problem I think I should be able to solve using Python but
> after having searched the internet for the better part of this
> evening my head spins and I would apreciate some guidance.
>
> Disclaimer
>
> My formal programming training happened 35+ years ago and
> initially involved F77 and later Pascal. Python is something
> I have picked up lately and for fun. I don't master Python by any
> stretch of imagination. I know some linear algebra and numerical
> methods but don't practice any of this on a daily basis...
>
> Problem background
>
> 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.
>
> My thinking so far
>
> I have played around a little with something called DSM
> https://en.wikipedia.org/wiki/Design_structure_matrix
> at work and think entering all wishes into a 2D array
> for further processing and overview should be a good idea.
>
> 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.
>
> Here is a picture that may help understanding what I am after:
> https://picasaweb.google.com/103341501341482571816/Miscellaneous#6177389865951753330
> In this example I have 25 individuals (each allowed two wishes),
> one 5-bed room, two 4-bed rooms and four 3-bed rooms.
> Wishes are marked by "1" so a wants to sleep in the same room
> as i and n etc. The rooms are shown as light grey squares
> along the diagonal. Scores to the right show how many wishes
> are fulfilled in each room and at the bottom right corner I
> have the total score. The goal is to re-shuffle the array
> to maximize this score.
>
> 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.
>
> TIA
>
> /Martin
>

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 :)

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence