时间戳

首页 > 解决方案 > 创建 Domino 列表

prolog - 创建 Domino 列表

问题描述

我正在尝试获得一个Domino带有列表的排序列表Domino

我的代码目前看起来像：

listdomino(_,[],[],[]).    
listdomino([I,J],M,Start,Fin):-
    (( member([J,K],M),
       delete(M,[J,K],M2),
       append([[J,K]],Fin1,Fin),
       listdomino([I,K],M2,Start,Fin1)
     )
   ;
    ( member([K,I],M),
      delete(M,[K,I],M2),
      append(Start1,[[K,I]],Start),
      listdomino([K,J],M2,Start1,Fin)
    )
   ).

listdominoSorted(X,M,Out):-
    append(Start,[X],K),
    append(K,Fin,Out),
    listdomino(X,M,Start,Fin).

实际结果：

?- listdominoSorted([1,2],[[2,1],[2,2]],L).
L = [[1, 2], [2, 2], [2, 1]] ;
L = [[2, 1], [1, 2], [2, 2]] ;
L = [[2, 1], [1, 2], [2, 2]] ;
L = [[2, 2], [2, 1], [1, 2]] ;

程序返回[[2, 1], [1, 2], [2, 2]]两次，之后不再退出。

期望的结果：

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

我怎么解决这个问题？

标签： prolog

解决方案

我看了你的代码一两分钟，但是在看到使用delete/3之后，警告铃声响了，我查看了其他示例。虽然这个相关的答案没有回答你的问题，但声明

我建议改为快速检查有效性，并让 Prolog 计算出插入点。

引导我尝试Prolog 非常适合的生成和测试方法。

首先是测试部分：

没有多米诺骨牌是有效的。

domino_test([]).

一张多米诺骨牌是有效的。

domino_test([[_,_]]).

当两个多米诺骨牌共享相同的计数 ( D_1) 时，它们是有效的。这是递归有效的。

domino_test([[_,D_1],[D_1,D_2]|T]) :-
  domino_test([[D_1,D_2]|T]).

接下来生成值。这实际上只是多米诺骨牌的排列。

?- permutation([[1,2],[2,1],[2,2]],P).
P = [[1, 2], [2, 1], [2, 2]] ;
P = [[1, 2], [2, 2], [2, 1]] ;
P = [[2, 1], [1, 2], [2, 2]] ;
P = [[2, 1], [2, 2], [1, 2]] ;
P = [[2, 2], [1, 2], [2, 1]] ;
P = [[2, 2], [2, 1], [1, 2]] ;
false.

将带有测试的排列放在一个谓词中给出：

list_domino(L,P) :-
  permutation(L,P),
  domino_test(P).

所有的代码

domino_test([]).

domino_test([[_,_]]).

domino_test([[_,D_1],[D_1,D_2]|T]) :-
  domino_test([[D_1,D_2]|T]).

list_domino(L,P) :-
  permutation(L,P),
  domino_test(P).

例子：

?- list_domino([[1,2],[2,1],[2,2]],P).
P = [[1, 2], [2, 2], [2, 1]] ;
P = [[2, 1], [1, 2], [2, 2]] ;
P = [[2, 2], [2, 1], [1, 2]] ;
false.

我怀疑您给定的测试用例是一个简单的案例，需要对此进行修改，但我会让您检查一下。

推荐阅读