How to rearrange array using Python?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
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? Hal Sent from Surface From: Mark Lawrence Sent: Thursday, July 30, 2015 3:21 PM To: python-list@python.org 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 -- https://mail.python.org/mailman/listinfo/python-list-- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
On 30/07/2015 23:31, ltc.hots...@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 :) -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
Den 2015-07-31 skrev Thomas 'PointedEars' Lahn : > 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
Den 2015-07-31 skrev 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? 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 > 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
Den 2015-07-31 skrev Martin Schöön : > Den 2015-07-31 skrev Thomas 'PointedEars' Lahn : >> 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
On Tue, Oct 20, 2015 at 12:57 PM, Martin Schöön wrote:
> 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?
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)
--
https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
On Tue, Oct 20, 2015 at 1:26 PM, Ian Kelly 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. -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
On Tue, 20 Oct 2015 20:01 Martin Schöön wrote: 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? 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: How to rearrange array using Python?
Den 2015-10-20 skrev Ian Kelly :
>>
>> 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
--
https://mail.python.org/mailman/listinfo/python-list
