PyCSP³

Constraint Cardinality

The constraint Cardinality, also called GlobalCardinality or gcc in the literature, ensures that the number of occurrences of each value in a specified set, taken by the variables of a specified list, is equal to a specified value (or variable), or belongs to a specified interval. A dictionay called occurrences is used to store that kind of information.

Below, we give several illustrations corresponding to representative use cases of the constraint Cardinality.

Case 1: Cardinality with Exact Numbers of Occurrences

We consider the case where we have a list of variables and a dictionay indicating for each value (key), the exact number of expected occurrences (value) with a constant.

To see how this constraint works, we need first to import the library PyCSP$^3$:

from pycsp3 import *

We introduce an array $x$ of $8$ variables, each one with {0,1,2,3} as domain.

x = VarArray(size=8, dom=range(4))

We can display (the structure of) the array as well as the domain of the first variable.

print("Array of variable x: ",x)
print("Domain of any variable: ", x[0].dom)

Array of variable x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]]
Domain of any variable:  0..3

We simply post a single constraint Cardinality:

the number of occurrences of the value 0 must be 1
the number of occurrences of the value 1 must be 2
the number of occurrences of the value 2 must be 3
the number of occurrences of the value 3 must be 2

satisfy(
    Cardinality(x, occurrences={0:1, 1:2, 2:3, 3:2})
);

By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can also print the values assigned to the variables in the found solution; we can call the function values() that collects the values assigned (in the last found solution) to a specified list of variables.

if solve() is SAT:
    print("Solution: ", values(x))

Solution:  [0, 1, 1, 2, 2, 2, 3, 3]

On can check that the number of solutions (supports) for our constraint is ${8 \choose 1} \times {7 \choose 2} \times {5 \choose 2}$

if solve(sols=ALL) is SAT:
    print("Last found solution: ", values(x))
    print("Number of solutions: ", n_solutions())

Last found solution:  [2, 2, 0, 2, 1, 3, 3, 1]
Number of solutions:  1680

Case 2: Cardinality with Ranges of Occurrences

We consider now the case where we have a list of variables and a dictionay indicating for each value (key), an interval of expected occurrences (value).

First of all, we need to remove everything that has been introduced so far.

unpost()

We control that there are no more constraints.

print(posted())

[]

We post a single constraint Cardinality:

the number of occurrences of the value 0 must be 1
the number of occurrences of the value 1 must be between 2 and 3
the number of occurrences of the value 2 must be between 2 and 3
the number of occurrences of the value 3 must be between 1 and 3

satisfy(
    Cardinality(x, occurrences={0:1, 1:range(2,4), 2:range(2,4), 3:range(1,4)})
);

Interstingly, we can display the internal representation of the posted constraint; although a little bit technical, we can see that the information about occurrences is correct.

print(posted())

cardinality(list:[x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]], values:[0, 1, 2, 3], occurs:[1, 2..3, 2..3, 1..3])

We can run again the solver.

if solve() is SAT:
    print("Solution: ", values(x))

Solution:  [0, 1, 1, 1, 2, 2, 2, 3]

And we can enumerate the 15 first solutions (supports) for this constraint.

if solve(sols=15) is SAT:
    for i in range(n_solutions()):
        print(f"Solution {i+1}: {values(x, sol=i)}")

Solution 1: [0, 1, 1, 1, 2, 2, 2, 3]
Solution 2: [0, 1, 1, 1, 2, 2, 3, 3]
Solution 3: [0, 1, 1, 1, 2, 2, 3, 2]
Solution 4: [0, 1, 1, 1, 2, 3, 3, 2]
Solution 5: [0, 1, 1, 1, 2, 3, 2, 2]
Solution 6: [0, 1, 1, 1, 2, 3, 2, 3]
Solution 7: [0, 1, 1, 1, 3, 2, 2, 3]
Solution 8: [0, 1, 1, 1, 3, 2, 2, 2]
Solution 9: [0, 1, 1, 1, 3, 3, 2, 2]
Solution 10: [0, 1, 1, 1, 3, 2, 3, 2]
Solution 11: [0, 1, 1, 2, 3, 2, 3, 2]
Solution 12: [0, 1, 1, 2, 3, 2, 1, 2]
Solution 13: [0, 1, 1, 2, 3, 3, 1, 2]
Solution 14: [0, 1, 1, 2, 3, 3, 2, 2]
Solution 15: [0, 1, 1, 2, 3, 1, 2, 2]

Case 3: Cardinality with a Variable Number of Occurrences

We consider now the case where we have a list of variables and a dictionay indicating for each value (key), a number of expected occurrences represented by a variable.

To start, we remove the last posted constraint by calling the function unpost().

unpost()

We control that there are no more constraints.

print(posted())

[]

We introduce a second array of variables $y$ that will be used to store the number of occurrences of each value.

y = VarArray(size=4, dom=range(9))

We post a single constraint Cardinality:

the number of occurrences of the value 0 must be $y[0]$
the number of occurrences of the value 1 must be $y[1]$
the number of occurrences of the value 2 must be $y[2]$
the number of occurrences of the value 3 must be $y[3]$

satisfy(
    Cardinality(x, occurrences={i:y[i] for i in range(4)})
);

We can display the internal representation of the posted constraint:

print(posted())

cardinality(list:[x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]], values:[0, 1, 2, 3], occurs:[y[0], y[1], y[2], y[3]])

We can run the solver.

if solve() is SAT:
    print("Solution: ", values(x))
    for v in range(4):
        print(f"The number of occurrences of {v} is {value(y[v])}")

Solution:  [0, 0, 0, 0, 0, 0, 0, 0]
The number of occurrences of 0 is 8
The number of occurrences of 1 is 0
The number of occurrences of 2 is 0
The number of occurrences of 3 is 0

One can anticipate that the number of solutions (supports) for this constraint is $4^8$.

if solve(sols=ALL) is SAT:
    print("Last found solution: ", values(x))
    print("Number of solutions: ", n_solutions())

Last found solution:  [3, 3, 1, 1, 0, 3, 2, 2]
Number of solutions:  65536

Constraint Cardinality

Case 1: Cardinality with Exact Numbers of Occurrences

Case 2: Cardinality with Ranges of Occurrences

Case 3: Cardinality with a Variable Number of Occurrences

Related Models