Constraint count

The constraint count, introduced in CHIP [BC94] and Sicstus [COC97], ensures that the number of variables in list which are assigned a value in values respects a numerical condition $(\odot,k)$ composed of an operator in {lt,le,ge,gt,eq,ne,in,notin} and a right operand which is an integer value, a variable, an integer interval or a set of integers. It is also present in Gecode with the same name and in the Global Constraints Catalog where it is called counts. This constraint captures known constraints atleast, atMost, exactly and among.

To simplify, we assume for the semantics that V is a set of integer values.

Syntax

<count>
  <list> (intVar wspace)2+ </list>
  <values> (intVal wspace)+ | (intVar wspace)+ </values> 
  <condition> "(" operator "," operand ")" </condition>
</count>

Below, c1 enforces that the number of variables in {v1,v2,v3,v4} that take the value of variable v must be different from the value of k1. Constraints c2, c3, c4 and c5 illustrate how to represent atleast, atMost, exactly and among.

• c2 represents among(k2, {w1, w2, w3, w4}, {1, 5, 8})
• c3 represents atLeast(k3, {x1, x2, x3, x4, x5}, 1)
• c4 represents atMost(2, {y1, y2, y3, y4}, 0)
• c5 represents exactly(k5, {z1, z2, z3}, z)

Example

<count id="c1">
  <list> v1 v2 v3 v4 </list>
  <values> v </values>
  <condition> (ne,k1) </condition>
</count>
<count id="c2">   <!-- among -->
  <list> w1 w2 w3 w4 </list>
  <values> 1 5 8 </values>
  <condition> (eq,k2) </condition>
</count>
<count id="c3">  <!-- atLeast -->
  <list> x1 x2 x3 x4 x5 </list>
  <values> 1 </values> 
  <condition> (ge,k3) </condition>
</count>
<count id="c4">  <!-- atMost -->
  <list> y1 y2 y3 y4 </list>
  <values> 0 </values>
  <condition> (le,2) </condition>
</count>
<count id="c5">  <!-- exactly -->
  <list> z1 z3 z3 </list>
  <values> z </values>  
  <condition> (eq,k5) </condition>
</count>