Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #94790 > unrolled thread

How to rearrange array using Python?

Back to article view | Back to comp.lang.python

Contents

  How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-07-30 20:31 +0000
    Re: How to rearrange array using Python? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-30 23:21 +0100
      Re: How to rearrange array using Python? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-31 04:29 +0200
        Re: How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-07-31 20:40 +0000
          Re: How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-08-17 21:14 +0000
            Re: How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-10-20 18:57 +0000
              Re: How to rearrange array using Python? Ian Kelly <ian.g.kelly@gmail.com> - 2015-10-20 13:26 -0600
                Re: How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-10-21 18:47 +0000
              Re: How to rearrange array using Python? Ian Kelly <ian.g.kelly@gmail.com> - 2015-10-20 13:28 -0600
    Re: How to rearrange array using Python? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-30 23:41 +0100
    Re: How to rearrange array using Python? Robin Koch <robin.koch@t-online.de> - 2015-07-31 03:18 +0200
      Re: How to rearrange array using Python? Martin Schöön <martin.schoon@gmail.com> - 2015-07-31 20:53 +0000

#94790 — 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

[toc] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#94796

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.

[toc] | [prev] | [next] | [standalone]

#94818

Den 2015-07-31 skrev Thomas 'PointedEars' Lahn <PointedEars@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

[toc] | [prev] | [next] | [standalone]

#95446

Den 2015-07-31 skrev Martin Schöön <martin.schoon@gmail.com>:
> Den 2015-07-31 skrev Thomas 'PointedEars' Lahn <PointedEars@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

[toc] | [prev] | [next] | [standalone]

#97841

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

[toc] | [prev] | [next] | [standalone]

#97842

On Tue, Oct 20, 2015 at 12:57 PM, Martin Schöön <martin.schoon@gmail.com> 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)

[toc] | [prev] | [next] | [standalone]

#97869

Den 2015-10-20 skrev Ian Kelly <ian.g.kelly@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

[toc] | [prev] | [next] | [standalone]

#97843

On Tue, Oct 20, 2015 at 1:26 PM, Ian Kelly <ian.g.kelly@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.

[toc] | [prev] | [next] | [standalone]

#94793

On 30/07/2015 23:31, ltc.hotspot@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

[toc] | [prev] | [next] | [standalone]

#94794

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

[toc] | [prev] | [next] | [standalone]

#94819

Den 2015-07-31 skrev Robin Koch <robin.koch@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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web