How to rearrange array using Python?

Martin Schöön martin.schoon at gmail.com
Thu Jul 30 22:31:44 CEST 2015


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


More information about the Python-list mailing list