Re: Re: ctypes typecasting in perl

[Shantanu Bhadoria]

Thanks Abigail,
That works perfectly. I had a inkling that the solution lies in pack
unpack. This is it.

>
> I think you want pack/unpack:
>
>   $ perl -E 'say unpack s => pack S => 64256'
>   -1280
>   $
>
>
> Abigail
>
>
> From: Yitzchak Scott-Thoennes 
>


> Abigail's pack/unpack suggestion will convert it after the fact, but I
> am wondering what you do to "read[ing] the register" to get an
> unsigned int in the first place.
>
> Hi Yitzchak,
I am working with I2C/SMBus devices but there weren't many modules offering
a easy interface for that on cpan that I was particularly pleased with. I
had to write my own based on libi2c-dev library called Device::SMBus
It doesn't expose all functions provided by smbus section of libi2c-dev but
it does provide most of the usable parts.
https://metacpan.org/module/Device::SMBus
I pushed it to CPAN a few days ago. I am planning to push
Device::LSM303DLHC and Device::L3GD30 public too since the last bit off
handicap I had is sorted out now.

In case you are curious, all this is to access altIMU Inertial measurement
unit which includes a LSM303 chip for magnetometer/accelerometer L3GD20
chip for gyroscope and a LPS331AP chip for barometer/altimeter for my
personal robotics project. Its a cheap piece of hardware for doing stuff by
yourself if you can't afford the more expensive IMU solutions in the
market. Only trouble being that you have to write the whole code, filtering
algorithms interfaces/API etc. yourself from the absolute raw data provided
by this chipset, which makes it a fun project for me.
Cheers,
-Shantanu Bhadoria

Re: Assigning Classes

[D Perrett]

I suspect this is the sort of problem where no solution will give you
consistently unremarkable results if in the long run there are any
unspoken requirements like 'students shouldn't be able to game the
system by lying about their preferences'.

Leaving that aside, a naive (computationally expensive) solution would
be to take all the combinations of assigning students to courses, rule
out the impossible, compute the 'optimability', and sort. That would
be vast, you'd start by creating an array of length @courses **
@students (more when you include the 'two courses' rule).

A better option (memorywise) might be to write a function that takes a
list of students and assigns them one by one, measuring the accrued
dissatisfaction as it goes. Where possible, it assigns people to where
they want to be. It rejects a solution if it finds at any point a) it
has empty classes and no students remaining; b) it has students
remaining, but no acceptable place to put them (e.g. if none of
choices 1-5 are present), or an unacceptable level of dissatisfaction
has been reached (e.g. it's already exceeded the dissatisfaction of
its best-case scenario so far). If a solution is rejected, it
backtracks to the last decision it made, and makes a different
decision. It will stop after either a) reaching a perfect solution (or
an acceptable solution, if you can come up with a tolerable score), or
b) running out of solutions. This would still be the same number of
end-solutions, and getting to each solution would be slower, but it
might not break trying to find an acceptable solution.

Another option that comes to mind is randomly allocating them all,
ensuring required conditions are filled, then iterate over the
students, probably starting with the most dissatisfied to begin with.
Where students are free to move without breaking required conditions,
they should move to the class they prefer. Otherwise, they should look
for trades (starting in their most preferred class). The trade need
not be mutually beneficial, but it should benefit the overall score.
Keep iterating over them all until things stabilise. Try this a few
times with different random starting points and see if and how the
score improves.

You could also try pulling some good results from the backtracker and
using them as bases for the trading mechanism.

I think the two courses rule is a complication that can be partially
by giving the most dissatisfied in the first course the first choice
in the second course. Although really, we should be optimising for
satisfaction across both courses simultaneously. which is still
possible if you're using the backtracker method - you keep going with
each solution, oonce you've allocated students in the first, you start
allocating students to the second (dissatisfied first) until you've
got a dissatisfaction figure for the two courses combined or until you
need to backtrack back into the first course.

Daniel

On 9 September 2013 18:17, Andrew Solomon  wrote:
> Hi Dave
>
> I think the area Raphael suggests is 'Integer Programming'.
>
> With a bit of luck you'll get acceptable results with *linear* integer
> programming using something like this:
>
> http://sourceforge.net/projects/lipside/
>
> but if you wind up getting the majority of students with exactly what they
> want and a few outliers getting neither of their choices (turning them into
> terrorists) you might have more luck with a non-linear integer programming
> solution.
>
> http://en.wikipedia.org/wiki/List_of_optimization_software
>
> If I were doing the non-linear thing I'd probably start experimenting with
> this:
>
> http://www.maplesoft.com/contact/webforms/maple_evaluation.aspx
>
> http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GlobalOptimization/GlobalSolveMatrixForm
>
> The fun bit will be modelling your problem into the structures these
> systems offer, but I'm pretty sure you can get a close match.
>
> Enjoy! :)
>
> Andrew
>
>
>
>
>
>
> On Mon, Sep 9, 2013 at 4:02 PM, Raphael Mankin  wrote:
>
>> Second thoughts: I was slightly wrong in my previous reply.
>>
>> This is not a 0/1 problem so the Hungarian does not apply. However it is
>> a general integer  transportation problem with limited link capacities.
>> The Hungarian would apply if you were assigning students to private
>> tutors; that is a 0/1 problem.
>>
>> Each student represents a bundle of k resources that have to be
>> 'transported' to the destinations (classes), where each student has to
>> attend k classes. k can be different for each student.
>>
>> Each destination has a capacity: the size of the class.
>>
>> Each 'link' joining a student to a class has a cost: the student's
>> unhappiness at taking that class. It also has a limiting capacity of 1
>> (a student can only attend a class once).
>>
>> A web search of 'integer transportation problems' will find the
>> algorithm.
>>
>> On Mon, 2013-09-09 at 12:45 +, Dave Cross wrote:
>> > I have offered to help a friend[1] solve what so

Re: Assigning Classes

[Avishalom Shalit]

I would agree that the problem is ill posed.

a formal (and therefor solvable ) definition would be e.g. by defining the
cost of a solution and minimizing it.
e.g. for each student, for each of his two courses  his personal cost  for
that course is the square of his raking.
(so if he ranked it 4, his cost for the course is 16)

now you can add the constraints as further "costs"

e.g. for every course with more than LIMIT students. you add 1000 *
(enrolled-LIMIT)^2
for every course with under 2 students you add 1*(2-number of students
in course)^2
you could add another term to compensate students. (e.g. every student with
a course rated 4 or 5 gets a (Course1rate+course2rate)^4 price)

sum over all prices, and minimize.*
but there needs to be a defined cost of getting the lower ranked classes,
and for "bumping" somone

* (e.g. by moving players at random, occasionally by switching players. and
if you end up with lower price, accept the change, if you raise the price,
revert with some probability (1-exp(-beta*deltaPrice)))





-- vish



On 9 September 2013 11:21, James Laver  wrote:

> On Mon, Sep 9, 2013 at 4:10 PM, Dave Cross  wrote:
> >
> > I'm pretty sure that Paul wasn't actually dismissing Prolog. I think
> you'll
> > find he was making a joke.
>
> ...which I should have gotten but I'm full of cold.
>
> James
>

Re: Assigning Classes

[Andrew Solomon]

Hi Dave

I think the area Raphael suggests is 'Integer Programming'.

With a bit of luck you'll get acceptable results with *linear* integer
programming using something like this:

http://sourceforge.net/projects/lipside/

but if you wind up getting the majority of students with exactly what they
want and a few outliers getting neither of their choices (turning them into
terrorists) you might have more luck with a non-linear integer programming
solution.

http://en.wikipedia.org/wiki/List_of_optimization_software

If I were doing the non-linear thing I'd probably start experimenting with
this:

http://www.maplesoft.com/contact/webforms/maple_evaluation.aspx

http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GlobalOptimization/GlobalSolveMatrixForm

The fun bit will be modelling your problem into the structures these
systems offer, but I'm pretty sure you can get a close match.

Enjoy! :)

Andrew






On Mon, Sep 9, 2013 at 4:02 PM, Raphael Mankin  wrote:

> Second thoughts: I was slightly wrong in my previous reply.
>
> This is not a 0/1 problem so the Hungarian does not apply. However it is
> a general integer  transportation problem with limited link capacities.
> The Hungarian would apply if you were assigning students to private
> tutors; that is a 0/1 problem.
>
> Each student represents a bundle of k resources that have to be
> 'transported' to the destinations (classes), where each student has to
> attend k classes. k can be different for each student.
>
> Each destination has a capacity: the size of the class.
>
> Each 'link' joining a student to a class has a cost: the student's
> unhappiness at taking that class. It also has a limiting capacity of 1
> (a student can only attend a class once).
>
> A web search of 'integer transportation problems' will find the
> algorithm.
>
> On Mon, 2013-09-09 at 12:45 +, Dave Cross wrote:
> > I have offered to help a friend[1] solve what sounds like an
> > interesting problem.
> >
> > She has a list of courses that are offered. Some of these courses have
> > a maximum class size and others are effectively infinite (I don't
> > believe that second part, but hey!) There are about thirty of these
> > courses.
> >
> > She also has a list of students who have decided which courses they
> > are interested in doing. For each student, we have their five
> > favourite choices - ranked from 1 to 5.
> >
> > The problem is, of course, to find the optimum arrangement of students
> > to courses so that each student is doing the course as close to their
> > first choice as possible.
> >
> > There are, however, a couple of extra constraints.
> >
> > 1/ Each course much be run with at least two students. So if there is
> > a course that has no students choosing it, two students must be
> > assigned to it.
> >
> > 2/ Each student actually does two courses. So if someone is forced
> > into a course because of rule 1 above, we can sweeten the pill
> > slightly by guaranteeing (insofar as we can) that they get their first
> > choice for their other course.
> >
> > I'm sure that most of this must be a previously solved problem. But
> > I'm not sure where to start looking.
> >
> > Any ideas would be much appreciated.
> >
> > Cheers,
> >
> > Dave...
> >
> > [1] And those of you who know that my wife is a teacher might well
> > draw conclusions about who that friend is :-)
> >
>
>
>

Re: ctypes typecasting in perl

[Yitzchak Scott-Thoennes]

On Mon, Sep 9, 2013 at 8:55 AM, Shantanu Bhadoria  wrote:
> I am trying to read registers off a chip which store data in
> int16_t format but since the data is in simple binary code, essentially
> when I read the register I get a simple unsigned int value from it.

Abigail's pack/unpack suggestion will convert it after the fact, but I
am wondering what you do to "read[ing] the register" to get an
unsigned int in the first place.

Re: ctypes typecasting in perl

[Jérôme Étévé]

Would that help?

http://perldoc.perl.org/perlpacktut.html

J.


On 9 September 2013 16:55, Shantanu Bhadoria  wrote:
> I have been playing around with talking to some IMU chips i.e gyroscopes,
> magnetometers and accelerometers from my raspberryPi and I am facing a
> slight problem which might seem trivial to those familiar more with C or XS
> code than I. I am trying to read registers off a chip which store data in
> int16_t format but since the data is in simple binary code, essentially
> when I read the register I get a simple unsigned int value from it. Is
> there a function or module in perl which would allow me to convert typecast
> something as int16_t?
>
> esentially in python the following gives me int 64256 typecast into c_int16
> and returns -1280.
> from ctypes import *
> print c_int16(64256).value
>
> Is there a equivalent function or module in perl that would do it? My
> thanks to whoever can help me solve this problem.
>
> Cheers,
> -Shantanu Bhadoria



-- 
Jerome Eteve
+44(0)7738864546
http://www.eteve.net/

Re: ctypes typecasting in perl

[Abigail]

On Mon, Sep 09, 2013 at 10:55:06PM +0700, Shantanu Bhadoria wrote:
> I have been playing around with talking to some IMU chips i.e gyroscopes,
> magnetometers and accelerometers from my raspberryPi and I am facing a
> slight problem which might seem trivial to those familiar more with C or XS
> code than I. I am trying to read registers off a chip which store data in
> int16_t format but since the data is in simple binary code, essentially
> when I read the register I get a simple unsigned int value from it. Is
> there a function or module in perl which would allow me to convert typecast
> something as int16_t?
> 
> esentially in python the following gives me int 64256 typecast into c_int16
> and returns -1280.
> from ctypes import *
> print c_int16(64256).value
> 
> Is there a equivalent function or module in perl that would do it? My
> thanks to whoever can help me solve this problem.


I think you want pack/unpack:

  $ perl -E 'say unpack s => pack S => 64256'
  -1280
  $


Abigail

ctypes typecasting in perl

[Shantanu Bhadoria]

I have been playing around with talking to some IMU chips i.e gyroscopes,
magnetometers and accelerometers from my raspberryPi and I am facing a
slight problem which might seem trivial to those familiar more with C or XS
code than I. I am trying to read registers off a chip which store data in
int16_t format but since the data is in simple binary code, essentially
when I read the register I get a simple unsigned int value from it. Is
there a function or module in perl which would allow me to convert typecast
something as int16_t?

esentially in python the following gives me int 64256 typecast into c_int16
and returns -1280.
from ctypes import *
print c_int16(64256).value

Is there a equivalent function or module in perl that would do it? My
thanks to whoever can help me solve this problem.

Cheers,
-Shantanu Bhadoria

Re: Assigning Classes

[James Laver]

On Mon, Sep 9, 2013 at 4:10 PM, Dave Cross  wrote:
>
> I'm pretty sure that Paul wasn't actually dismissing Prolog. I think you'll
> find he was making a joke.

...which I should have gotten but I'm full of cold.

James

Re: Assigning Classes

[Paul Johnson]

On Mon, Sep 09, 2013 at 03:10:14PM +, Dave Cross wrote:
> Quoting James Laver :
> 
> >On Mon, Sep 9, 2013 at 2:57 PM, Paul Johnson  wrote:
> >>On Mon, Sep 09, 2013 at 01:30:00PM +, Dave Hodgkinson wrote:
> >>>Prolog. Facts and rules then go solve.
> >>
> >>no
> >
> >Actually, Prolog was my first thought too. The major limitation is
> >fallback behaviour.
> 
> I'm pretty sure that Paul wasn't actually dismissing Prolog. I think
> you'll find he was making a joke.

You're far too kind.

-- 
Paul Johnson - p...@pjcj.net
http://www.pjcj.net

Re: Assigning Classes

[Abigail]

On Mon, Sep 09, 2013 at 12:45:43PM +, Dave Cross wrote:
>
> I have offered to help a friend[1] solve what sounds like an interesting 
> problem.
>
> She has a list of courses that are offered. Some of these courses have a 
> maximum class size and others are effectively infinite (I don't believe 
> that second part, but hey!) There are about thirty of these courses.
>
> She also has a list of students who have decided which courses they are 
> interested in doing. For each student, we have their five favourite 
> choices - ranked from 1 to 5.

The point is, every student gets to follow just one course?

> The problem is, of course, to find the optimum arrangement of students  
> to courses so that each student is doing the course as close to their  
> first choice as possible.

That's ill defined. What is "as close to their first choice as possible"?
Say there are two solutions that differ only in the following:
Solution A) has student 1 get to their first pick, and student 2 to their
fourth pick. Solution B) has student 1 and student 2 doing their second pick.
Is any of those solutions to be preferred? If so, why? Is a first-first-fifth
solution to be preferred over a second-third-third? Over a third-third-third?

> There are, however, a couple of extra constraints.
>
> 1/ Each course much be run with at least two students. So if there is a 
> course that has no students choosing it, two students must be assigned to 
> it.
>
> 2/ Each student actually does two courses. So if someone is forced into a 
> course because of rule 1 above, we can sweeten the pill slightly by 
> guaranteeing (insofar as we can) that they get their first choice for 
> their other course.
>
> I'm sure that most of this must be a previously solved problem. But I'm 
> not sure where to start looking.

I don't think this would be an NP-complete problem (although it probably
is if the number of courses each student is taken isn't fixed), but
I'd think it's still computational heavy. I doubt a greedy algorithm is
going to work.

However, it sounds like a problem that will have a fast and relative
simple solution using heuristics that will give a close to perfect answer
in all but a few cases.


Abigail

Re: Assigning Classes

[Dave Cross]

Quoting James Laver :


On Mon, Sep 9, 2013 at 2:57 PM, Paul Johnson  wrote:

On Mon, Sep 09, 2013 at 01:30:00PM +, Dave Hodgkinson wrote:

Prolog. Facts and rules then go solve.


no


Actually, Prolog was my first thought too. The major limitation is
fallback behaviour.


I'm pretty sure that Paul wasn't actually dismissing Prolog. I think  
you'll find he was making a joke.


Dave...

Re: Assigning Classes

[Raphael Mankin]

Second thoughts: I was slightly wrong in my previous reply.

This is not a 0/1 problem so the Hungarian does not apply. However it is
a general integer  transportation problem with limited link capacities.
The Hungarian would apply if you were assigning students to private
tutors; that is a 0/1 problem.

Each student represents a bundle of k resources that have to be
'transported' to the destinations (classes), where each student has to
attend k classes. k can be different for each student.

Each destination has a capacity: the size of the class.

Each 'link' joining a student to a class has a cost: the student's
unhappiness at taking that class. It also has a limiting capacity of 1
(a student can only attend a class once).

A web search of 'integer transportation problems' will find the
algorithm.

On Mon, 2013-09-09 at 12:45 +, Dave Cross wrote:
> I have offered to help a friend[1] solve what sounds like an  
> interesting problem.
> 
> She has a list of courses that are offered. Some of these courses have  
> a maximum class size and others are effectively infinite (I don't  
> believe that second part, but hey!) There are about thirty of these  
> courses.
> 
> She also has a list of students who have decided which courses they  
> are interested in doing. For each student, we have their five  
> favourite choices - ranked from 1 to 5.
> 
> The problem is, of course, to find the optimum arrangement of students  
> to courses so that each student is doing the course as close to their  
> first choice as possible.
> 
> There are, however, a couple of extra constraints.
> 
> 1/ Each course much be run with at least two students. So if there is  
> a course that has no students choosing it, two students must be  
> assigned to it.
> 
> 2/ Each student actually does two courses. So if someone is forced  
> into a course because of rule 1 above, we can sweeten the pill  
> slightly by guaranteeing (insofar as we can) that they get their first  
> choice for their other course.
> 
> I'm sure that most of this must be a previously solved problem. But  
> I'm not sure where to start looking.
> 
> Any ideas would be much appreciated.
> 
> Cheers,
> 
> Dave...
> 
> [1] And those of you who know that my wife is a teacher might well  
> draw conclusions about who that friend is :-)
> 

Re: Assigning Classes

[James Laver]

On Mon, Sep 9, 2013 at 2:57 PM, Paul Johnson  wrote:
> On Mon, Sep 09, 2013 at 01:30:00PM +, Dave Hodgkinson wrote:
>> Prolog. Facts and rules then go solve.
>
> no

Actually, Prolog was my first thought too. The major limitation is
fallback behaviour.

James

Re: Assigning Classes

[Dirk Koopman]

On 09/09/13 15:10, Raphael Mankin wrote:

This is a classic variation of the transportation problem.

If you can assign (different) costs to being in the wrong class and zero
cost to being in the right class then the Hungarian Algorithm will do
the job.

The standard version of the algorithm has quartic time complexity, but
there is a version due to Wright(?) at Lancaster University that is
quadratic. Both versions have quadratic space complexity. I programmed
it about 20 years ago but I cannot now give you any references. Search
the literature.



It also has similarities to rate minimisation problems in chemistry 
where one has several (say) gases, some energy, reactions happen and one 
has (essentially) guess what is likely to come out. Or alternatively: 
given what comes out and the starting proportions, how did it get there.


The NAG libraries have a raft of numercial algorithms for solving these 
sorts of problems - I always found the ones that used (cough) "Monte 
Carlo Methods" gave what seemed like the best answers and in (by far) 
the quickest time. I believe that after 30 odd years in the wilderness 
this type of algorithm is coming back into fashion as is worth a long.


Dirk

Re: Assigning Classes

[Raphael Mankin]

This is a classic variation of the transportation problem.

If you can assign (different) costs to being in the wrong class and zero
cost to being in the right class then the Hungarian Algorithm will do
the job.

The standard version of the algorithm has quartic time complexity, but
there is a version due to Wright(?) at Lancaster University that is
quadratic. Both versions have quadratic space complexity. I programmed
it about 20 years ago but I cannot now give you any references. Search
the literature.

On Mon, 2013-09-09 at 09:16 -0400, Mark Fowler wrote:
> On Monday, 9 September 2013 at 08:45, Dave Cross wrote:
> > I have offered to help a friend[1] solve what sounds like an 
> > interesting problem.
> 
> No idea on the literature, but here's my two pence worth:
>  
> I'd start by putting everyone in their favourite choice of classes, and 
> seeing how "bad" that is.  I assume since you're asking the question that's 
> not a possible solution.
> 
> How feasible is it to randomly select students and move them and see how that 
> works?  I ask because this is what we'd do before we had computers, but with 
> a computer you could do this a million times a second and try out all the 
> possibilities (it's key to limit the number of moves to narrow the problem 
> space so we don't have to wait for the heat death of the universe first - 
> hence the putting everyone in the "optimal but broken" place to start with.)  
> You'd need a "unhappiness" score for a student which could be computed from 
> the distance they are from their "ideal" courses.  You might want to look at 
> adding some sort of power rule to the distance too, since you'd probably be 
> better off with a bunch of slightly unhappy students verses all happy but one 
> very screwed over student.  Obviously junk any 'solution' that doesn't meet 
> your class criteria.
> 
> Mark.
> 
> 

Re: Assigning Classes

[Paul Johnson]

On Mon, Sep 09, 2013 at 01:30:00PM +, Dave Hodgkinson wrote:
> Prolog. Facts and rules then go solve.

no

-- 
Paul Johnson - p...@pjcj.net
http://www.pjcj.net

Re: Assigning Classes

[Dave Hodgkinson]

Prolog. Facts and rules then go solve.



On Mon, Sep 9, 2013 at 12:45 PM, Dave Cross  wrote:

>
> I have offered to help a friend[1] solve what sounds like an interesting
> problem.
>
> She has a list of courses that are offered. Some of these courses have a
> maximum class size and others are effectively infinite (I don't believe
> that second part, but hey!) There are about thirty of these courses.
>
> She also has a list of students who have decided which courses they are
> interested in doing. For each student, we have their five favourite choices
> - ranked from 1 to 5.
>
> The problem is, of course, to find the optimum arrangement of students to
> courses so that each student is doing the course as close to their first
> choice as possible.
>
> There are, however, a couple of extra constraints.
>
> 1/ Each course much be run with at least two students. So if there is a
> course that has no students choosing it, two students must be assigned to
> it.
>
> 2/ Each student actually does two courses. So if someone is forced into a
> course because of rule 1 above, we can sweeten the pill slightly by
> guaranteeing (insofar as we can) that they get their first choice for their
> other course.
>
> I'm sure that most of this must be a previously solved problem. But I'm
> not sure where to start looking.
>
> Any ideas would be much appreciated.
>
> Cheers,
>
> Dave...
>
> [1] And those of you who know that my wife is a teacher might well draw
> conclusions about who that friend is :-)
>
>

Re: Assigning Classes

[Mark Fowler]

On Monday, 9 September 2013 at 08:45, Dave Cross wrote:
> I have offered to help a friend[1] solve what sounds like an 
> interesting problem.

No idea on the literature, but here's my two pence worth:
 
I'd start by putting everyone in their favourite choice of classes, and seeing 
how "bad" that is.  I assume since you're asking the question that's not a 
possible solution.

How feasible is it to randomly select students and move them and see how that 
works?  I ask because this is what we'd do before we had computers, but with a 
computer you could do this a million times a second and try out all the 
possibilities (it's key to limit the number of moves to narrow the problem 
space so we don't have to wait for the heat death of the universe first - hence 
the putting everyone in the "optimal but broken" place to start with.)  You'd 
need a "unhappiness" score for a student which could be computed from the 
distance they are from their "ideal" courses.  You might want to look at adding 
some sort of power rule to the distance too, since you'd probably be better off 
with a bunch of slightly unhappy students verses all happy but one very screwed 
over student.  Obviously junk any 'solution' that doesn't meet your class 
criteria.

Mark.

Assigning Classes

[Dave Cross]

I have offered to help a friend[1] solve what sounds like an  
interesting problem.


She has a list of courses that are offered. Some of these courses have  
a maximum class size and others are effectively infinite (I don't  
believe that second part, but hey!) There are about thirty of these  
courses.


She also has a list of students who have decided which courses they  
are interested in doing. For each student, we have their five  
favourite choices - ranked from 1 to 5.


The problem is, of course, to find the optimum arrangement of students  
to courses so that each student is doing the course as close to their  
first choice as possible.


There are, however, a couple of extra constraints.

1/ Each course much be run with at least two students. So if there is  
a course that has no students choosing it, two students must be  
assigned to it.


2/ Each student actually does two courses. So if someone is forced  
into a course because of rule 1 above, we can sweeten the pill  
slightly by guaranteeing (insofar as we can) that they get their first  
choice for their other course.


I'm sure that most of this must be a previously solved problem. But  
I'm not sure where to start looking.


Any ideas would be much appreciated.

Cheers,

Dave...

[1] And those of you who know that my wife is a teacher might well  
draw conclusions about who that friend is :-)