<jupyter_start><jupyter_text>Some common 'tricks'When modelling problems in ASP, it turns out that there are some 'tricks' that come in handy a lot of the time. Here we'll run through some of the most common of these tricks.Let's start with setting up a function to print answer sets of a program:<jupyter_code>import clingo

def print_answer_sets(program):
    control = clingo.Control()
    control.add("base", [], program)
    control.ground([("base", [])])
    control.configuration.solve.models = 0
    for model in control.solve(yield_=True):
        sorted_model = [str(atom) for atom in model.symbols(shown=True)]
        sorted_model.sort()
        print("Answer set: {{{}}}".format(", ".join(sorted_model)))<jupyter_output><empty_output><jupyter_text>Generating The following tricks are useful for generating the right search space. Generating assignments to binary variablesYou can generate all assignments to a set of binary variables as follows (e.g., truth assignments).<jupyter_code>print_answer_sets("""
    var(1..3).
    true(X) :- not false(X), var(X).
    false(X) :- not true(X), var(X).
    #show true/1.
    #show false/1.
""")<jupyter_output>Answer set: {false(1), false(2), false(3)}
Answer set: {false(1), false(3), true(2)}
Answer set: {false(1), false(2), true(3)}
Answer set: {false(1), true(2), true(3)}
Answer set: {false(2), false(3), true(1)}
Answer set: {false(2), true(1), true(3)}
Answer set: {false(3), true(1), true(2)}
Answer set: {true(1), true(2), true(3)}<jupyter_text>Or alternatively like this:<jupyter_code>print_answer_sets("""
    var(1..3).
    1 { true(X); false(X) } 1 :- var(X).
    #show true/1.
    #show false/1.
""")<jupyter_output>Answer set: {false(2), false(3), true(1)}
Answer set: {false(3), true(1), true(2)}
Answer set: {false(2), true(1), true(3)}
Answer set: {true(1), true(2), true(3)}
Answer set: {false(1), false(2), true(3)}
Answer set: {false(1), false(2), false(3)}
Answer set: {false(1), true(2), true(3)}
Answer set: {false(1), false(3), true(2)}<jupyter_text>Generating assignments to $n$-ary variablesGenerating all assignments to variables with domains of more than two elements, you can do like this:<jupyter_code>print_answer_sets("""
    var(1..2).
    value(1..4).
    assign(X,V) :- var(X), value(V), not assign(X,V') : value(V'), V' != V.
    #show assign/2.
""")<jupyter_output>Answer set: {assign(1,1), assign(2,3)}
Answer set: {assign(1,1), assign(2,2)}
Answer set: {assign(1,1), assign(2,1)}
Answer set: {assign(1,1), assign(2,4)}
Answer set: {assign(1,4), assign(2,1)}
Answer set: {assign(1,2), assign(2,1)}
Answer set: {assign(1,3), assign(2,1)}
Answer set: {assign(1,2), assign(2,3)}
Answer set: {assign(1,2), assign(2,2)}
Answer set: {assign(1,2), assign(2,4)}
Answer set: {assign(1,4), assign(2,2)}
Answer set: {assign(1,3), assign(2,2)}
Answer set: {assign(1,4), assign(2,4)}
Answer set: {assign(1,4), assign(2,3)}
Answer set: {assign(1,3), assign(2,4)}
Answer set: {assign(1,3), assign(2,3)}<jupyter_text>Or a bit more compactly/intuitively, like this:<jupyter_code>print_answer_sets("""
    var(1..2).
    value(1..4).
    1 { assign(X,V) : value(V) } 1 :- var(X).
    #show assign/2.
""")<jupyter_output>Answer set: {assign(1,3), assign(2,4)}
Answer set: {assign(1,3), assign(2,1)}
Answer set: {assign(1,3), assign(2,2)}
Answer set: {assign(1,3), assign(2,3)}
Answer set: {assign(1,4), assign(2,4)}
Answer set: {assign(1,4), assign(2,2)}
Answer set: {assign(1,4), assign(2,3)}
Answer set: {assign(1,4), assign(2,1)}
Answer set: {assign(1,2), assign(2,3)}
Answer set: {assign(1,2), assign(2,1)}
Answer set: {assign(1,2), assign(2,4)}
Answer set: {assign(1,2), assign(2,2)}
Answer set: {assign(1,1), assign(2,3)}
Answer set: {assign(1,1), assign(2,4)}
Answer set: {assign(1,1), assign(2,2)}
Answer set: {assign(1,1), assign(2,1)}<jupyter_text>Generating one-to-one assignmentsIf you have two sets of equal size, and you want to generate all one-to-one assignments between these sets, you can do that as follows:<jupyter_code>print_answer_sets("""
    side1(1..3).
    side2(a;b;c).
    1 { match(S1,S2) : side1(S1) } 1 :- side2(S2).
    1 { match(S1,S2) : side2(S2) } 1 :- side1(S1).
    #show match/2.
""")<jupyter_output>Answer set: {match(1,c), match(2,b), match(3,a)}
Answer set: {match(1,c), match(2,a), match(3,b)}
Answer set: {match(1,b), match(2,c), match(3,a)}
Answer set: {match(1,b), match(2,a), match(3,c)}
Answer set: {match(1,a), match(2,c), match(3,b)}
Answer set: {match(1,a), match(2,b), match(3,c)}<jupyter_text>Generating one-to-many assignmentsIf you have two sets $S_1$ and $S_2$ (possibly of different size), and you want to generate all assignments where every element in $S_1$ is assigned to exactly one element in $S_2$ (but not vice versa), then this is a way to do that:<jupyter_code>print_answer_sets("""
    side1(1..2).
    side2(a;b;c).
    1 { match(S1,S2) : side2(S2) } 1 :- side1(S1).
    #show match/2.
""")<jupyter_output>Answer set: {match(1,c), match(2,a)}
Answer set: {match(1,c), match(2,b)}
Answer set: {match(1,c), match(2,c)}
Answer set: {match(1,b), match(2,a)}
Answer set: {match(1,b), match(2,c)}
Answer set: {match(1,b), match(2,b)}
Answer set: {match(1,a), match(2,a)}
Answer set: {match(1,a), match(2,b)}
Answer set: {match(1,a), match(2,c)}<jupyter_text>Generating arbitrary assignmentsIf you have two sets $S_1$ and $S_2$ (possibly of different size), and you want to generate *all possible* (partial) assignments, you can do this:<jupyter_code>print_answer_sets("""
    side1(1..2).
    side2(a;b).
    { match(S1,S2) : side1(S1) } :- side2(S2).
    #show match/2.
""")<jupyter_output>Answer set: {}
Answer set: {match(1,b)}
Answer set: {match(2,a)}
Answer set: {match(1,b), match(2,a)}
Answer set: {match(2,b)}
Answer set: {match(2,a), match(2,b)}
Answer set: {match(1,b), match(2,b)}
Answer set: {match(1,b), match(2,a), match(2,b)}
Answer set: {match(1,a)}
Answer set: {match(1,a), match(1,b)}
Answer set: {match(1,a), match(2,b)}
Answer set: {match(1,a), match(1,b), match(2,b)}
Answer set: {match(1,a), match(2,a)}
Answer set: {match(1,a), match(2,a), match(2,b)}
Answer set: {match(1,a), match(1,b), match(2,a)}
Answer set: {match(1,a), match(1,b), match(2,a), match(2,b)}<jupyter_text>Generating injective assignmentsIf you have two sets $S_1$ and $S_2$ (possibly of different size), and you want to generate all assignments where every element in $S_1$ is assigned to exactly one element in $S_2$ (but not vice versa) that are *injective* (i.e., no two elements in $S_1$ are assigned to the same element of $S_2$), you can do that as follows:<jupyter_code>print_answer_sets("""
    side1(1..2).
    side2(a;b;c).
    { match(S1,S2) : side1(S1) } 1 :- side2(S2).
    1 { match(S1,S2) : side2(S2) } 1 :- side1(S1).
    #show match/2.
""")<jupyter_output>Answer set: {match(1,c), match(2,a)}
Answer set: {match(1,c), match(2,b)}
Answer set: {match(1,b), match(2,a)}
Answer set: {match(1,b), match(2,c)}
Answer set: {match(1,a), match(2,b)}
Answer set: {match(1,a), match(2,c)}<jupyter_text>Generating arbitrary subsetsSelecting an arbitrary subset of elements from a given set can be done as follows:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(b)}
Answer set: {select(c)}
Answer set: {select(b), select(c)}
Answer set: {select(a)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>Or alternatively like this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) : element(E) }.
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(b)}
Answer set: {select(c)}
Answer set: {select(b), select(c)}
Answer set: {select(a)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>Generating subsets of size $k$If you want to generate all subsets that are of size *exactly* $k$, you can do this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    2 { select(E) : element(E) } 2.
    #show select/1.
""")<jupyter_output>Answer set: {select(b), select(c)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}<jupyter_text>Generating subsets of size $\leq k$If you want to generate all subsets that are of size *at most* $k$, you can do this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) : element(E) } 2.
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(c)}
Answer set: {select(b)}
Answer set: {select(b), select(c)}
Answer set: {select(a)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(c)}<jupyter_text>Generating subsets of size $\geq k$If you want to generate all subsets that are of size *at least* $k$, you can do this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    2 { select(E) : element(E) }.
    #show select/1.
""")<jupyter_output>Answer set: {select(b), select(c)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b), select(c)}
Answer set: {select(a), select(b)}<jupyter_text>ConstraintsThe following tricks are useful for filtering out incorrect solutions, after you have generated a search space.We will illustrate these with the example case where we generated an arbitrary subset of elements, but the same tricks apply also to the other cases. Basic constraintsIf you want to ensure that `something` is **true**, you can add the constraint `:- not something.` (which can be read as: "It is not the case that `something` is not true").For example, if you want to ensure that `a` is selected, you can use `:- not select(a).`.<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- not select(a).
    
    #show select/1.
""")<jupyter_output>Answer set: {select(a)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>If you want to ensure that `something` is **false**, you can add the constraint `:- something.` (which can be read as: "It is not the case that `something` is true").For example, if you want to ensure that `a` is **not** selected, you can use `:- select(a).`.<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- select(a).
    
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(c)}
Answer set: {select(b)}
Answer set: {select(b), select(c)}<jupyter_text>AND-constraintsIf you want to ensure that both `thing1` and `thing2` are true, you can define a new predicate (e.g., `my_property`), add rules that express that `my_property` is true if both `thing1` and `thing2` are true, and add a constraint that says that `my_property` must be true.For example:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    my_property :- select(a), select(b).
    :- not my_property.
    
    #show select/1.
""")<jupyter_output>Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>This strategy (of defining a new predicate, defining when exactly this predicate is true, and requiring it to be true) works for more complicated cases as well.In this simple example, we could easily have done without the new predicate too, e.g.:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- not select(a).
    :- not select(b).
    
    #show select/1.
""")<jupyter_output>Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>OR-constraintsIf you want to ensure that `thing1` is true **or** `thing2` is true, you can use the strategy of introducing a new predicate, like this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    my_property :- select(a).
    my_property :- select(b).
    :- not my_property.
    
    #show select/1.
""")<jupyter_output>Answer set: {select(b)}
Answer set: {select(b), select(c)}
Answer set: {select(a)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>Or you can add a constraint `:- not thing1, not thing2.` (which can be read as: "It is not the case that both `thing1` is false and `thing2` is false").For example:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- not select(a), not select(b).
    
    #show select/1.
""")<jupyter_output>Answer set: {select(b)}
Answer set: {select(b), select(c)}
Answer set: {select(a)}
Answer set: {select(a), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>IMPLIES-constraintsIf you want to express that if `thing1` is true, then also `thing2` must be true, you can do that like this, for example:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- select(a), not select(b).
    
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(c)}
Answer set: {select(b)}
Answer set: {select(b), select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}<jupyter_text>Again, also here the strategy of defining a new predicate would work well. IF-AND-ONLY-IF-constraintsIf you want to express that two things must either both be true, or both be false, you can do that by using two 'if-then' constraints. For example like this:<jupyter_code>print_answer_sets("""
    element(a;b;c).
    { select(E) } :- element(E).
    
    :- select(a), not select(b).
    :- not select(a), select(b).
    
    #show select/1.
""")<jupyter_output>Answer set: {}
Answer set: {select(c)}
Answer set: {select(a), select(b)}
Answer set: {select(a), select(b), select(c)}
StarcoderdataJupyterStructuredCleanDedup