How to rearrange array using Python?

[Martin Schöön]

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

[Mark Lawrence]

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

[Mark Lawrence]

On 30/07/2015 23:31, ltc.h...@gmail.com wrote:
> Hi Mark,
>
> I’m still confused because line 4 reads: fh=open(fname,'r') # Open a new
> file handle, not fn = open(fname)
>
> Can you write down line by line from error to correction?
>

I'd think about it if you could find the correct thread :)

[Robin Koch]

Am 30.07.2015 um 22:31 schrieb Martin Schöön:

> Scores to the right show how many wishes are fulfilled in each room

Is it possible the is a mistake in the sum column on the third row?
Should the be a 1?

> The goal is to re-shuffle the array to maximize this score.
>
> How do I go about doing that?

Depending on how you store those wishes I'd think you can use
random.shuffle()!?

But do you think simply maximising the score is the optimal solution to
the problem?
That way some kids will get their both wishes fulfilled (s, e and p in
your example), while other kids not even one (r, z, j, v, c, y, g, m, d).
Shouldn't be the goal to maximise the number of kinds which get at least
one wished kid in the same room? (I hesitate writing "friend", since you
maybe wouldn't want to be picked by someone... Friend would be pairs of
kids picking each other. Another thing one might want to takeinto
account. :-))

--
Robin Koch

[Thomas 'PointedEars' Lahn]

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.

[Martin Schöön]

Den 2015-07-31 skrev Thomas 'PointedEars' Lahn <Point...@web.de>:

> Mark Lawrence wrote:
>>
>> 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-
>

Thanks guys, I will follow up on the CSP lead. It is not something I
have prior experience of so it will be interesting.

> Please trim your quotes to the relevant minimum.
>

Indeed.

/Martin

[Martin Schöön]

Den 2015-07-31 skrev Robin Koch <robin...@t-online.de>:
> Am 30.07.2015 um 22:31 schrieb Martin Schöön:
>
>> Scores to the right show how many wishes are fulfilled in each room
>
> Is it possible the is a mistake in the sum column on the third row?
> Should the be a 1?

Indeed.

>
>> The goal is to re-shuffle the array to maximize this score.
>>
>> How do I go about doing that?
>
> Depending on how you store those wishes I'd think you can use
> random.shuffle()!?

When cruising the net yesterday I came across this and it looked to me
it does re-shuffle arrays but not in a way that helps me. Maybe I
am wrong.

>
> But do you think simply maximising the score is the optimal solution to
> the problem?

It is a start. The result will no doubt need some human post-processing.
I am merely hoping to eliminate the grunt-work.

(There will be pre-processing too, correcting misspelled names etc...)

> That way some kids will get their both wishes fulfilled (s, e and p in

<snip>

> kids picking each other. Another thing one might want to takeinto
> account. :-))
>

I did hint at differences between my example and the real problem...

/Martin

[Martin Schöön]

Den 2015-07-31 skrev Martin Schöön <martin...@gmail.com>:
> Den 2015-07-31 skrev Thomas 'PointedEars' Lahn <Point...@web.de>:
>> Mark Lawrence wrote:
>>>
>>> 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-
>>
> Thanks guys, I will follow up on the CSP lead. It is not something I
> have prior experience of so it will be interesting.
>

Brief progress report (just to tell you that your advice has been
'absorbed').

I have been reading a bit, here is one example.
http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html
Interesting stuff but sometimes head-spinning -- I don't always follow
the lingo.

I have also downloaded and installed Python-Constraint. It works as
advertised as long as I replicate the examples found at:
http://labix.org/python-constraint
I can even scale some of the examples.

Creating my own examples has proven harder -- in part because the
documentation is minimalistic but also because I have not tried very
hard. We have, finally, got some nice summer weather here...

I have tried my hand at a *very* basic room placement problem. It
works
apart from the fact that I have not figured out how to tell the solver
there are limits to how many occupants each room can house.

Yesterday I started on a basic Kenken example. I need to experiment
a little to find a way to add the needed division and subtraction
constraints. I haven't given this much thought yet.

Today I found Numberjack:
http://numberjack.ucc.ie/
It seems better documented than Python-Constraint but that is all
I know. Anyone with experience of Numberjack?

In summary: I am having fun using ipython and org-mode for emacs.
I am not making much headway but then I don't have a dead-line
:-)

/Martin

[Martin Schöön]

It has been a while.
I have mastered solving Kenken and Sudoku using Python-constraint.

I still have no clue on how to tell the solver how to constrain
the number of occupants in rooms: I have made up an simple example
with nine persons and three rooms. Wishes for room mates are
mild in the extreme so it is very easy for a human to place these
nine persons in the three three-bed rooms such that all wishes are
fulfilled. Python-constraint set up by me finds 27 solutions of
which most place more than three persons in at least one room.

Anyone into CSP willing to offer me a hint?

/Martin

[Ian Kelly]

I assume that your variables are the individuals and the domains of
those variables are the rooms. Based on the python-constraint docs,
your constraint could look something like this:

from collections import Counter

ROOM_SIZE = {
'A': 3,
'B': 3,
'C': 4,
'D': 4,
'E': 5,
}

def room_size_constraint(*v):
counter = Counter(v.values())
return all(count <= ROOM_SIZE[room]
for room, count in counter.items())

problem.addConstraint(room_size_constraint)

[Ian Kelly]

On Tue, Oct 20, 2015 at 1:26 PM, Ian Kelly <ian.g...@gmail.com> wrote:
> def room_size_constraint(*v):
> counter = Counter(v.values())

Sorry, this should just be Counter(v), since v here is a tuple, not a dict.

[Oscar Benjamin]

How have you defined your constraints? How have you defined the variables you want to solve for?

Do you know whether or not the real problem you want to solve typically has any solutions satisfying all constraints? It won't be possible to answer that question a priori without looking at the data and the approach to take differs substantially if the system is overdetermined.

Another approach BTW would be to model the wishes as a directed graph with children as vertices and wishes as arcs. This way you can partition the graph into weakly connected components so that your problem is reduced to placing components into rooms rather than individuals.

--
Oscar

[Martin Schöön]

Den 2015-10-20 skrev Ian Kelly <ian.g...@gmail.com>:
>>
>> Anyone into CSP willing to offer me a hint?
>
> I assume that your variables are the individuals and the domains of
> those variables are the rooms. Based on the python-constraint docs,
> your constraint could look something like this:
>
> from collections import Counter
>
> ROOM_SIZE = {
> 'A': 3,
> 'B': 3,
> 'C': 4,
> 'D': 4,
> 'E': 5,
> }
>
> def room_size_constraint(*v):
> counter = Counter(v.values())
> return all(count <= ROOM_SIZE[room]
> for room, count in counter.items())
>
> problem.addConstraint(room_size_constraint)

Bingo!
Just what I needed but didn't know where to look for. Now I 'only' have
to read
https://docs.python.org/dev/library/collections.html#counter-objects
to understand what's really going on in the code :-)

Then I will try less benign examples.

/Martin