时间戳

首页 > 解决方案 > Prolog 排列调度

recursion - Prolog 排列调度

问题描述

我有以下带有谓词参加的文件，这表示每个学生都参加了某门课程（第一个参数：Student_ID，第二个参数：Course_ID）。

attends(476, c216).
attends(478, c216).
attends(484, c216).
attends(487, c216).
attends(491, c216).

我想要做的是创建一个谓词函数，它创建一个包含 3 个列表（A、B、C）和课程的考试时间表。

每个列表都象征着一周。然后，例如为了找到适合大多数学生的最佳时间表，它以 3-3-2 的形式打印出所有不同的课程排列：

[c204,c209,c210]列表 A 是第一周的第一个案例中的课程。

清单 B 是第 2 周等...

?- schedule(A,B,C).
A = [c204,c209,c210],
B = [c212,c214,c216],
C = [c217,c218];

A = [c204,c209,c210],
B = [c212,c214,c216],
C = [c218,c217];

问题1：

那么，我怎样才能采用参加/ 2 谓词并仅将第二个参数转换为列表，以使列表包含已声明的所有课程。

例如：L = [c212,c213...]。

问题2：

排列将使用名为 k_permutation/3 的自定义函数完成：

delete(E,L,NL):-
  append(L1,[E|L2],L),
  append(L1,L2,NL).


k_permutation(0,_,[]).
k_permutation(K,L1,[X|T2]) :-
  K > 0,
  K1 is K - 1,
  delete(X,L1,L2),
  k_permutation(K1,L2,T2).

但由于某种原因，这个自定义函数 (k_permutation/3) 运行无限时间。函数递归有问题吗？该功能应该如何使用？

标签： recursionprologschedulingplanning

解决方案

至于问题1，简单的方法是：

collect_courses(L1):- findall(Course, attends(_,Course), L), sort(L,L1).

L将有出现在 中的所有课程attends/2，因此会有重复，这就是我们使用sort/2删除重复项的原因。

至于问题2，首先Swi-Prolog已经有了delete/3predicate的定义，所以我建议你重命名它。除此之外k_permutations/2工作正常：

?- k_permutation(2,[1,2,3],L).
L = [1, 2] ;
L = [1, 3] ;
L = [2, 1] ;
L = [2, 3] ;
L = [3, 1] ;
L = [3, 2] ;
false.

推荐阅读