CODEWITHSUNDEEP
combinatoricsanswer-set-programmingclingo
exchez
exchez

Reputation: 503

Generating Solution Candidates For Matching People in Clingo/ASP

I have a list of people and I want to pair them all then do some filtering based on preferences. When I generate my candidate solutions, how do I avoid creating candidate solutions that re-pair a people.

For example:

person(a;b;c;d) .
{match(X, Y): person(Y)}1 :- person(X) .

This generates candidate solutions that include match(a,b) match(c,b) ...

I would like ONLY candidate solutions that do not rematch anyone like: match(a,b) match(c,d) ...

My goal is to not have to filter rematches out via additional constraints. Also, not everyone needs to be matched. Thanks!

Upvotes: 2

Views: 434

Answers (2)

Duda
Duda

Reputation: 3746

I'd go for Max Ostrowskis answer.

One of the difficulties is to handle the order of the attributes for the match predicate: this is a tuple, there is a difference if your value shows up on first or second position. Adding a rule to make the predicate commutative should do the trick since you don't need to distinguish for a value to be on first or second position. This method does not use a constraint (on first sight), but it duplicates the generated values so the output differs from your desired solution. Also it adds a line to the code.

person(a;b;c;d).
{match(X,Y): person(Y), X!=Y}1 :- person(X).
match(Y,X) :- match(X,Y).
#show match/2.

Output

Answer: 1

Answer: 2
match(c,a) match(a,c)
Answer: 3
match(b,a) match(a,b)
Answer: 4
match(c,d) match(d,c)
Answer: 5
match(b,a) match(a,b) match(c,d) match(d,c)
Answer: 6
match(b,d) match(d,b)
Answer: 7
match(c,a) match(a,c) match(b,d) match(d,b)
Answer: 8
match(b,c) match(c,b)
Answer: 9
match(d,a) match(a,d)
Answer: 10
match(d,a) match(a,d) match(b,c) match(c,b)
SATISFIABLE

Upvotes: 1

Max Ostrowski
Max Ostrowski

Reputation: 623

person(a;b;c;d).
{match(A,B) : person(A), person(B), A < B}.
:- person(A), 1 < {match(A,B); match(B,A)}.

You exclude solutions that have more than 1 match for a single person.

It is not possible to simply choose a correct set of atoms without additional constraints. As match(a,b) and match(b,c) can occur in different answer sets, both variables need to be created. Only a constraint can rule out that both do not occur in the same answer set.

Also note that your generator rule

{match(X, Y): person(Y)}1 :- person(X) .

already is a shortcut writing for

{match(X, Y): person(Y)} :- person(X).
:- person(X), 2 {match(X, Y): person(Y)}.

And therefore you are already using a constraint whenever your generator choice rule has non-trivial bounds.

PS: Check the different versions using --stats=2 for constraint count and --text for a rough approximation of what kind of constraints are generated.

Upvotes: 4

Related Questions