prolog - 通过从每个列表中选择 1 个元素来创建一个列表（序言）

Question

我有一个包含列表的列表。我想创建一个排列列表。

例子：

generate_perm([[3],[1,2,3,4],[1,2]], P).
P = [[3,1,1], [3,2,1], [3,3,1], [3,4,1], [3,1,2], [3,2,2], [3,3,2], [3,4,2]];
no

所以输出列表：第 n 个元素是输入列表中第 n 个列表的元素。我已经尝试过：使用成员和 findall，但我被卡住了。由于我是 prolog 的新手，所以我总是迫切地想。

到目前为止，我的代码提供了 1 个解决方案：

generate_perm([],_).
generate_perm([H|Tl], Perm):- member(M, H), append(Perm, [M], Perm2),
                              generate_perm(Tl, Perm2).

调试这个：

| ?- generate_perm([[3],[1,2,3,4],[1,2]], P).
 #      1      1 Call: member(_4961,[3]) ? 
 #      1      1 Exit: member(3,[3]) ? 
 #      2      1 Call: generate_perm([[1,2,3,4],[1,2]],[3]) ? 
 #      3      2 Call: member(_56173,[1,2,3,4]) ? 
?#      3      2 Exit: member(1,[1,2,3,4]) ? 
 #      4      2 Call: generate_perm([[1,2]],[3,1]) ? 
 #      5      3 Call: member(_138349,[1,2]) ? 
?#      5      3 Exit: member(1,[1,2]) ? 
 #      6      3 Call: generate_perm([],[3,1,1]) ? 
 #      6      3 Exit: generate_perm([],[3,1,1]) ? 
?#      4      2 Exit: generate_perm([[1,2]],[3,1]) ? 
?#      2      1 Exit: generate_perm([[1,2,3,4],[1,2]],[3]) ? 
P = [] ? 

所以答案就在那里（调用：generate_perm([],[3,1,1])，这里的答案是[3,1,1]），但它给了我一个空列表，我想不通为什么。我需要帮助的另一个步骤是我不知道如何在一个列表中获得所有解决方案。

标签： prolog

Answer 1

就像说的那样，“命令式思维”通常不适用于 Prolog。您应该根据（递归）定义进行思考。

例如，我们可以说crossprod/2第一个列表为空的地方产生了一个解决方案：空列表，因此我们可以将其指定为：

crossprod([], []).

现在我们仍然需要提出一个归纳案例：假设我们可以为n-1 个元素的列表生成排列，那么我们应该如何为n 个元素的列表（n≥0）生成排列。

对于这样的列表，我们在这里有第一个元素（“head”），head 是一个列表（因为第一个参数应该是一个列表的列表）。所以我们可以使用member/2获取子列表的一个元素，该元素将是结果列表的头部（第一项），然后我们递归地传递尾部（剩余的子列表）crossprod/2来生成结果的尾部，例如：

crossprod([H|T], [X|R]) :-
    member(X, H),
    crossprod(T, R).

或全部，这给出：

crossprod([], []).
crossprod([H|T], [X|R]) :-
    member(X, H),
    crossprod(T, R).

所以现在我们可以生成给定“集合”列表的“叉积”项目，例如：

?- crossprod([[3],[1,2,3,4],[1,2]], P).
P = [3, 1, 1] ;
P = [3, 1, 2] ;
P = [3, 2, 1] ;
P = [3, 2, 2] ;
P = [3, 3, 1] ;
P = [3, 3, 2] ;
P = [3, 4, 1] ;
P = [3, 4, 2].

如果我们然后想要生成这些列表（这很奇怪，通常最好独立生成答案），我们可以使用findall/3：

generate_perm(S, R) :- findall(Ri, crossprod(S, Ri), R)。

然后我们获得交叉产品列表，例如：

?- generate_perm([[3],[1,2,3,4],[1,2]], P).
P = [[3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 3, 1], [3, 3, 2], [3, 4|...], [3|...]].