Daniel Lyons
Daniel Lyons

Reputation: 22803

What is the best way to establish one-to-one pairings in clingo?

In wanting to create a set of pairings, I see in the textbook Answer Set Programming that the following definition occurs in Listing 3.1:

#const n=6.

% at(G,C) means that guest G is assigned chair C.
{at(G,1..n)} = 1 :- G = 1..n.
% achieved: each guest is assigned a chair.

G1 = G2 :- at(G1, C), at(G2, C).
% achieved: different guests are assigned different chairs.

I believe the first definition arises from the definition of an surjective function and the second from the definition of an injective function. If you have both, you have a bijection, which is what you want if the answer set consists of one-to-one pairings.

However, the same can be achieved by saying that that the second set is a surjection on the first:

#const n=6.

% at(G,C) means that guest G is assigned chair C.
{at(G,1..n)} = 1 :- G = 1..n.
% achieved: each guest is assigned a chair.

{at(1..n,C)} = 1 :- C = 1..n.
% achieved: different guests are assigned different chairs.

This doesn't seem to change the possible answer sets, although the order in which they are tried might be different—I notice that the first solution in the first fragment is at(1,1) at(2,2), at(3,3)... whereas the first solution in the second fragment is at(6,1) at(5,2) at(4,3)....

Is there a technical reason to prefer one definition over the other? My gut feeling is that repeating the first line for each dimension in which we want to create tuples is less error-prone than the second, if I wanted to establish triples or more, but that there is not a technical reason to go one way or the other.

Upvotes: 0

Views: 12

Answers (0)

Related Questions