Re: How to find combination of list elements in Prolog?

On 16/03/2014, at 9:07 AM, goktugerce . wrote:

> Hey guys, I'm new to prolog and kinda stuck in my homework. Here is my
> sample knowledge base:
> 
> course(tk222-1, [m-3, m-4]).
> course(tk222-2, [m-5, m-6]).
> course(tk222-3, [t-3, t-4]).
> course(tk222-4, [t-5, t-6]).
> course(tk222-5, [m-3, m-4]).
> course(cmpe230-1, [m-5, m-6, t-4]).
> course(fa489-1, [w-3, w-4])
> 
> tk222, cmpe230 and fa489 are courses, tk222-1, tk222-2, tk222-3, tk222-4,
> tk222-5, cmpe230-1 and fa489-1 are sections. Lists are the sections' course
> days and hours, as you can understand. Two sections are conflicting if they
> have class in the same day and same hour.

Unless you are using þ for Thursday, you might want
to reconsider using single letters for day names.

I actually feel quite unhappy about this data design already.
It is set up to make the question "what sessions does Section
use" easy to answer but the question "what sections are
scheduled in Session" hard.  I'd probably go with something
like

	course_section(tk222, tk222_1).
	...
	section_slot(tk222_1, m3).
	section_slot(tk222_1, m4).
	...
	slot_day_hour(m3, monday, 3).
	...

> And a plan is conflicting if it
> has two or more conflicting sections.

And what is a plan?


Supposing that a plan is a list of sections,

	conflicting_sections(S1, S2) :-
	    section_slot(S1, Slot),
	    section_slot(S2, Slot),
	    S1 \== S2.

(If this reminds you of "sibling", it should.)

	includes_conflicting_sections(Plan) :-
	    append(_, [S1|Rest], Plan),
	    member(S2, Rest),
	    conflicting_sections(S1, S2).

Here we appeal to the symmetry of conflicting_sections/2.
If Plan = [...,S1,...,S2,...], then having tests S1, S2
there is no point in testing S2, S1.


> My problem is to write a predicate as follows:
> 
> findNonConflictingPlans(+CourseList, -PlanList)
> ?- findNonConflictingPlans([fa489, tk222, cmpe230], PlanList).
> PlanList = [[fa489-1, tk222-1, cmpe230-1], [fa489-1, tk222-4,
> cmpe230-1], [fa489-1, tk222-5, cmpe230-1]]
> 
> How can I find combinations of courses in *CourseList* list and gather them
> together in *PlanList*?

Assuming that finding a plan means picking a section
for each course,

	course_plan([], []).
	course_plan([Course|Courses], [Section|Sections]) :-
	    course_section(Course, Section),
	    course_plan(Courses, Sections).

	course_safe_plan(Courses, Plan) :-
	    course_plan(Courses, Plan),
	    \+ includes_conflicting_sections(Plan).

The problem with this is that if Courses = [C1,...,Cn]
and course Ci has Ni sections, then there are
N1*...*Nn plans, so this is basically an exponential time
algorithm.

That's not really surprising, because this is a combinatorial
problem, akin to graph colouring and set cover.  It may be
that the number of combinations is only a few thousand million,
in which case, no worries.

Another way to talk about this is that we have a
"generate and test" pattern here: first we generate
a complete plan and then we test it.

It's practically always a good idea to push tests early.
In this case, when you are about to try the next Course,
you want to pick a Section that does not conflict with
any previously picked section.

	course_safe_plan(Courses, Plan) :-
	    extend_safe_plan(Courses, [], Plan).

	extend_safe_plan([], Plan, Final_Plan) :-
	    reverse(Plan, Final_Plan).
	extend_safe_plan([Course|Courses], Plan, Final_Plan) :-
	    /* pick a section */
	    course_section(Course, Section),
	    /* that does not conflict with any previous choice */
	    \+ ( member(S1, Plan),
	         section_slot(S1, Slot),
		 section_slot(Section, Slot)
	       ),
	    /* and try to fill in the remaining courses */
	    extend_safe_plan(Courses, [Section|Plan], Final_Plan).

(If this reminds you of n-queens, it should.)

There are a number of techniques that can be applied by hand
to solve the problem more efficiently still.

For one thing, you could represent a set of slots as a bitmask
in which case you can check for conflict with
	section_bits(Section, Bits),
	Bits /\ Bits_For_Current_Plan =:= 0
(In SWI Prolog you have to use the -O command line flag for
this to be efficient.)

You could of course use the constraint satisfaction support in
SWI Prolog to write a predicate that sets up a network of
"no conflict" constraints and then relies on the constraint
library to solve it, but I've taken a more elementary approach
here.