如何验证坐标是否在列表中 [英] How can I verify if a coordinate is in a list

问题描述

我正在生成随机坐标并添加到我的列表中，但首先我需要验证该坐标是否已存在.我正在尝试使用 member 但在调试时我发现它不起作用:

I'm generating random coordinates and adding on my list, but first I need verify if that coordinate already exists. I'm trying to use member but when I was debugging I saw that isn't working:

我的代码基本上是这样的:

My code is basically this:

% L is a list and Q is a count that define the number of coordinate
% X and Y are the coordinate members
% check if the coordniate already exists
% if exists, R is 0 and if not, R is 1
createCoordinates(L,Q) :-
    random(1,10,X),
    random(1,10,Y),
    convertNumber(X,Z),
    checkCoordinate([Z,Y],L,R),
    (R is 0 -> print('member'), createCoordinates(L,Q); print('not member'),createCoordinates(L,Q-1).

checkCoordinate(C,L,R) :-
    (member(C,L) -> R is 0; R is 1).

% transforms the number N in a letter L
convertNumber(N,L) :-
    N is 1, L = 'A';
    N is 2, L = 'B';
    ...
    N is 10, L = 'J'.

%call createCoordinates
createCoordinates(L,20).

当我调试时，这是输出:

When I was debugging this was the output:

在这张图片中，我在第一次交互中，L 是空的，所以 R 应该是 1 但始终是 0，坐标始终是列表的一部分.我的印象是 member 子句在我的列表中添加坐标并且没有意义

In this picture I'm in the firts interation and L is empty, so R should be 1 but always is 0, the coordinate always is part of the list. I have the impression that the member clause is adding the coordinate at my list and does'nt make sense

推荐答案

首先，我建议将您的问题分解成更小的部分.您应该有一个制作随机坐标的程序:

First off, I would recommend breaking your problem down into smaller pieces. You should have a procedure for making a random coordinate:

random_coordinate([X,Y]) :- 
    random(1, 10, XN), convertNumber(XN, X), 
    random(1, 10, Y).

其次，你的 checkCoordinate/3 正在将 Prolog 的成功/失败转换成一个整数，这对 Prolog 来说只是忙碌的工作，并没有真正改善你的生活.memberchk/2 完全可以满足您的任务(member/2 也可以使用，但比必要的功能更强大).这里真正的问题不是 member/2 没有工作，而是你试图在出路时建立这个列表参数，但你需要它在路上存在以检查

Second, your checkCoordinate/3 is converting Prolog's success/failure into an integer, which is just busy work for Prolog and not really improving life for you. memberchk/2 is completely sufficient to your task (member/2 would work too but is more powerful than necessary). The real problem here is not that member/2 didn't work, it's that you are trying to build up this list parameter on the way out, but you need it to exist on the way in to examine it.

我们通常在 Prolog 中通过添加第三个参数并在通过的过程中将值添加到列表中来解决此类问题.基本情况然后将该列表与出站列表等同起来，我们用一个较低数量的程序保护整个事物.换句话说，我们这样做:

We usually solve this kind of problem in Prolog by adding a third parameter and prepending values to the list on the way through. The base case then equates that list with the outbound list and we protect the whole thing with a lower-arity procedure. In other words, we do this:

random_coordinates(N, Coordinates) :- random_coordinates(N, [], Coordinates).

random_coordinates(0, Result, Result).
random_coordinates(N, CoordinatesSoFar, FinalResult) :- ...

现在我们有两件事，memberchk/2 应该按照我们需要的方式工作:

Now that we have two things, memberchk/2 should work the way we need it to:

random_coordinates(N, CoordinatesSoFar, FinalResult) :- 
   N > 0, succ(N0, N),   % count down, will need for recursive call
   random_coordinate(Coord),
   (memberchk(Coord, CoordinatesSoFar) -> 
       random_coordinates(N, CoordinatesSoFar, FinalResult)
   ;
       random_coordinates(N0, [Coord|CoordinatesSoFar], FinalResult)
   ).

这似乎是我们想要的:

?- random_coordinates(10, L), write(L), nl.
[[G,7],[G,3],[H,9],[H,8],[A,4],[G,1],[I,9],[H,6],[E,5],[G,8]]

?- random_coordinates(10, L), write(L), nl.
[[F,1],[I,8],[H,4],[I,1],[D,3],[I,6],[E,9],[D,1],[C,5],[F,8]]

最后，我注意到你继续使用这个语法:N is 1, ....我提醒您，这对我来说似乎是一个错误，因为 this 和 N = 1 之间没有区别，并且您的谓词可能会用这个来表达，这有点令人厌烦:

Finally, I note you continue to use this syntax: N is 1, .... I caution you that this looks like an error to me because there is no distinction between this and N = 1, and your predicate could be stated somewhat tiresomely just with this:

convertNumber(1, 'A').
convertNumber(2, 'B').
...

我倾向于使用 char_code/2 进行计算，但这种结构实际上可能更好.

My inclination would be to do it computationally with char_code/2 but this construction is actually probably better.

另一个提示您做错的提示是 L 到 createCoordinates/2 的参数在所有情况下都会传递，并且在任何情况下都不会被检查.在 Prolog 中，我们经常有一些看起来只是无意义传递的变量，但它们通常会改变位置或被多次使用，如 random_coordinates(0, Result, Result);虽然那里似乎没有发生任何事情，但实际发生的是管道:内置参数成为结果值.直接在那里的变量没有发生任何有趣的事情，但它正在被探测.但是在您的代码中 L 没有发生任何事情，除了据说它正在检查新坐标.但是您实际上从未向其附加任何内容，因此没有理由期望任何内容都会在 L 中结束.

Another hint that you are doing something wrong is that the parameter L to createCoordinates/2 gets passed along in all cases and is not examined in any of them. In Prolog, we often have variables that appear to just be passed around meaninglessly, but they usually change positions or are used multiple times, as in random_coordinates(0, Result, Result); while nothing appears to be happening there, what's actually happening is plumbing: the built-up parameter becomes the result value. Nothing interesting is happening to the variable directly there, but it is being plumbed around. But nothing is happening at all to L in your code, except it is supposedly being checked for a new coordinate. But you're never actually appending anything to it, so there's no reason to expect that anything would wind up in L.

编辑 请注意，@lambda.xy.x 通过在子句的头部添加新坐标并仅在主体中的递归调用之后检查列表来解决他们的答案中的问题，从而避免需要第二个列表参数.

Edit Notice that @lambda.xy.x solves the problem in their answer by prepending the new coordinate in the head of the clause and examining the list only after the recursive call in the body, obviating the need for the second list parameter.

Edit 2 也看看@lambda.xy.x 的其他解决方案，因为它在 N 接近 100 时具有更好的时间复杂度.

Edit 2 Also take a look at @lambda.xy.x's other solution as it has better time complexity as N approaches 100.

这篇关于如何验证坐标是否在列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！