0

I'm building an exam scheduler in Prolog. The scheduler is based on this example: https://metacpan.org/source/DOUGW/AI-Prolog-0.741/examples/schedule.pl

How can I make sure there are no permutations in my solution?

For example solution

-> ((exam1, teacher1, time1, room1), (exam2, teacher2, time2, room2))

Later solution:

-> ((exam2, teacher2, time2, room2),(exam1, teacher1, time1, room1))

How can I avoid this? Thanks!

Ken Vernaillen
  • 859
  • 1
  • 7
  • 37

1 Answers1

0

1) The closest/easiest from what you've got is to check that the course you've chosen is strictly bigger in order than the previous one.

For example by adding an extra predicate which also includes the previous course in the combination.

%%makeListPrev(PreviousTakenCourse, ResultCombinationOfCourses, NrOfCoursesToAdd)
makeListPrev(_,[], 0). 
makeListPrev(course(Tprev,Ttime,Troom),[course(Teacher,Time,Room)|Rest], N) :- 
    N > 0,
    teacher(Teacher), 
    classtime(Time),
    classroom(Room), 
    course(Tprev,Ttime,Troom) @< course(Teacher,Time,Room), %% enforce unique combinations
    is(M,minus(N,1)), 
    makeListPrev(course(Teacher,Time,Room),Rest,M).

In this way you eliminate all duplicate permutations of the same combination by always taking the lexographically smallest.

E.g if you have 4 courses:

(a,b,c,d)
(a,b,d,c) % d can't be before c
(a,c,b,d) % c can't be before b
...

2) Another way to solve this quite easily is to first create a list of all possible courses. And then take out all possible combinations of N sequentially.

scheduler(L) :- 
    %% Find all possible courses
    findall(course(Teacher,Time,Room),(teacher(Teacher),classtime(Time),classroom(Room)),Courses), 
    makeList(Courses,4,L),
    different(L).
makeList([],0,[]) :- !. %% list completed
makeList([H|T],N,[H|Res]) :- %% list including H
    M is N-1, 
    makeList(T,M,Res).
makeList([_|T], N, Res) :- makeList(T, N, Res). %% list without H
Sam Segers
  • 1,951
  • 2
  • 22
  • 28
  • 2
    (1) doesn't work: Instead of `(<)/2` use `(@<)/2`! This works for arbitrary terms, not just arithmetic expressions. Also, `Tprev`, `Ttime`, and `Troom` need to be "threaded through" so one list element can be compared to preceeding ones. – repeat Dec 24 '15 at 06:19
  • 1
    Thanks for checking. Although I tested it in swipl where it did work that way. Not sure what you mean with "threaded through"? – Sam Segers Dec 24 '15 at 09:15
  • 1
    For the clause (1) of `makeList/3` I get the warning `Singleton variables: [Tprev,Ttime,Troom]`. As said variables only occur once, each one of them is like `_`. So the test you are doing effectively is `c(_,_,_) @< c(x,y,z)`. That test is **always** true due to the standard order of terms (cf. http://www.swi-prolog.org/pldoc/man?section=standardorder or https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/ref_002dlte_002dcte_002dsot.html) – repeat Dec 24 '15 at 11:18
  • With threading I meant passing data about the previous element to the next recursion step. This technique is commonly called "lagging", cf http://stackoverflow.com/a/29164060/4609915 and http://stackoverflow.com/a/29868394/4609915 and http://stackoverflow.com/a/29869325/4609915 and http://stackoverflow.com/a/32027317/4609915 and http://stackoverflow.com/a/29844776/4609915 and http://stackoverflow.com/questions/3965054/prolog-find-minimum-in-a-list/3966139. – repeat Dec 24 '15 at 11:21
  • Does the first solution only check the previous solution with the next? Or all the previous solutions? Because I have +-1000000 solutions. – Ken Vernaillen Dec 24 '15 at 11:37
  • @repeat Damn, you're right I copied the wrong predicate in (1). I only noticed it now, will fix. – Sam Segers Dec 24 '15 at 11:39
  • @Ken the goal of the first solution is to have no permutations of the same solution. By always taking the lexographically first permuation of the solution, I'll add this to my answer. – Sam Segers Dec 24 '15 at 11:42
  • @SamSegers Aren't you checking permutations in the list of courses instead of checking the permutations of the solutionlist of lists of courses? – Ken Vernaillen Dec 24 '15 at 11:58
  • As in your question "((exam1, teacher1, time1, room1), (exam2, teacher2, time2, room2))" will be taken and "((exam2, teacher2, time2, room2),(exam1, teacher1, time1, room1))" won't considering that exam2 @> exam1. Try this? – Sam Segers Dec 24 '15 at 12:02
  • The code (2) does not make much sense to me. I read your code as: (a) build cross product of `Teacher * Time * Room`, (b) take a 4-element subsequence, (3) ensure the picked elements are non-overlapping. Is this it? Why 4? – repeat Dec 24 '15 at 12:14
  • 1
    No need to cut `(!)/0` here. – repeat Dec 24 '15 at 12:14
  • `(@<)/2` does not suffice to ensure that schedule comprises non-overlapping parts only. – repeat Dec 24 '15 at 12:16
  • @repeat It is based on the link in the question. Still I'm just trying to provide an answer to the question. – Sam Segers Dec 24 '15 at 12:36
  • @repeat If you don't cut, I suppose we will have a lot of useless calculations where N < 0 which we know will never be valid. Right? – Sam Segers Dec 24 '15 at 12:40
  • Simply add a goal `N > 0` to the recursive clauses. Don't cut. It breaks the code in lots of subtle ways. – repeat Dec 24 '15 at 15:14
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/98923/discussion-between-sam-segers-and-repeat). – Sam Segers Dec 24 '15 at 15:32
  • Prolog code can have both declarative and procedural semantics. Declarative semantics focuses on "what does it mean", procedural semantics on "how does execution proceed". While every programming language has procedural semantics, having both is a big part of what makes Prolog special. – repeat Dec 24 '15 at 19:40
  • Using cut can easily break the declarative semantics. It is more scalpel than pair of scissors. For good ideas on how to use `!/0` I recommend "The Craft of Prolog" by Richard O'Keefe. If you don't have a copy at hand, nevermind! Here a centre point of it... As a rule of thumb, rearrange the unifications in a clause suchthat only input unification occur before the cut and all output unification occur after the cut. Why? To preserve steadfastness, that is to ensure that more specialized uses of some goal gives us sensible results. Consider: http://swish.swi-prolog.org/p/makelist-xmas1.swinb HTH – repeat Dec 24 '15 at 19:43