How can I verify if a coordinate is in a list

问题:

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:

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

回答1:

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).

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.

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) :- ...

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)
   ).

And this seems to do what we want:

?- 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]]

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').
...

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

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.

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 Also take a look at @lambda.xy.x's other solution as it has better time complexity as N approaches 100.

回答2:

Since i had already written it, here is an alternative solution: The building block is gen_coord_notin/2 which guarantees a fresh solution C with regard to an exclusion list Excl.

gen_coord_notin(C, Excl) :-
    random(1,10,X),
    random(1,10,Y),
    ( memberchk(X-Y, Excl) ->
      gen_coord_notin(C, Excl)
    ;
      C = X-Y
    ).

The trick is that we only unify C with the new result, if it is fresh. Then we only have to fold the generations into N iterations:

gen_coords([], 0).
gen_coords([X|Xs], N) :-
    N > 0,
    M is N - 1,
    gen_coords(Xs, M),
    gen_coord_notin(X, Xs).

Remark 1: since coordinates are always 2-tuples, a list representation invites unwanted errors (e.g. writing [X|Y] instead of [X,Y]). Traditionally, an infix operator like - is used to seperate tuples, but it's not any different than using coord(X,Y).

Remark 2: this predicate is inherently non-logical (i.e. calling gen_coords(X, 20) twice will result in different substitutions for X). You might use the meta-level predicates var/1, nonvar/1, ground/1, integer, etc. to guard against non-sensical calls like gen_coord(1-2, [1-1]).

Remark 3: it is also important that the conditional does not have multiple solutions (compare member(X,[A,B]) and memberchk(X,[A,B])). In general, this can be achieved by calling once/1 but there is a specialized predicate memberchk/2 which I used here.

回答3:

I just realized that the performance of my other solutions is very bad for N close to 100. The reason is that with diminishing possible coordinates, the generate and test approach will take longer and longer. There's an alternative solution which generates all coordinates and picks N random ones:

all_pairs(Ls) :-
    findall(X-Y, (between(1,10,X), between(1,10,Y)), Ls).

remove_index(X,[X|Xs],Xs,0).
remove_index(I,[X|Xs],[X|Rest],N) :-
    N > 0,
    M is N - 1,
    remove_index(I,Xs,Rest,M).

n_from_pool(_Pool, [], 0).
n_from_pool(Pool, [C|Cs], N) :-
    N > 0,
    M is N - 1,
    length(Pool, L),
    random(0,L,R),
    remove_index(C,Pool,NPool,R),
    n_from_pool(NPool, Cs, M).

gen_coords2(Xs, N) :-
    all_pairs(Pool),
    n_from_pool(Pool, Xs, N).

Now the query

?- gen_coords2(Xs, 100).
Xs = [4-6, 5-6, 5-8, 9-6, 3-1, 1-3, 9-4, 6-1, ... - ...|...] ;
false.

succeeds as expected. The error message

?- gen_coords2(Xs, 101). ERROR: random/1: Domain error: not_less_than_one' expected, found0'

when we try to generate more distinct elements than possible is not nice, but better than non-termination.