5.278. same_modulo

Origin

Derived from same.

Constraint

same_modulo​(VARIABLES1,​VARIABLES2,​M)​

Argument(s)

VARIABLES1	collection​(var−dvar)​
VARIABLES2	collection​(var−dvar)​
M	int

Restriction(s)

|VARIABLES1|=|VARIABLES2|

required​(VARIABLES1,​var)​

required​(VARIABLES2,​var)​

M>​0

Purpose

For each integer R in ​[0,​M−1]​, let N1_R (respectively N2_R) denote the number of variables of VARIABLES1 (respectively VARIABLES2) that have R as a rest when divided by M. For all R in ​[0,​M−1]​ we have that N1_R=N2_R.

Example

( 〈1,​9,​1,​5,​2,​1〉,​ 〈6,​4,​1,​1,​5,​5〉,​3 )

The values of the first collection 〈1,​9,​1,​5,​2,​1〉 are respectively associated with the equivalence classes 1 mod 3=1, 9 mod 3=0, 1 mod 3=1, 5 mod 3=2, 2 mod 3=2, 1 mod 3=1. Therefore the equivalence classes 0, 1, and 2 are respectively used 1, 3, and 2 times. Similarly, the values of the second collection 〈6,​4,​1,​1,​5,​5〉 are respectively associated with the equivalence classes 6 mod 3=0, 4 mod 3=1, 1 mod 3=1, 1 mod 3=1, 5 mod 3=2, 5 mod 3=2. Therefore the equivalence classes 0, 1, and 2 are respectively used 1, 3, and 2 times. Consequently the same_modulo constraint holds. Figure 5.278.1 illustrates this correspondence.

Figure 5.278.1. Correspondence between the equivalence classes associated with collection 〈1,​9,​1,​5,​2,​1〉 and with collection 〈6,​4,​1,​1,​5,​5〉

Used in

k_same_modulo.

See also

same.

Key words

characteristic of a constraint: modulo.

combinatorial object: permutation.

constraint arguments: constraint between two collections of variables.

Arc input(s)

VARIABLES1 VARIABLES2

Arc generator

PRODUCT↦collection​(variables1,​variables2)​

Arc arity

2

Arc constraint(s)

variables1.var mod M=variables2.var mod M

Graph property(ies)

• for all connected components: NSOURCE=NSINK

• NSOURCE=|VARIABLES1|

• NSINK=|VARIABLES2|

---

Graph model

Parts (A) and (B) of Figure 5.278.2 respectively show the initial and final graph associated with the Example slot. Since we use the NSOURCE and NSINK graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. The same_modulo constraint holds since:

• Each connected component of the final graph has the same number of sources and of sinks.

• The number of sources of the final graph is equal to |VARIABLES1|.

• The number of sinks of the final graph is equal to |VARIABLES2|.

Figure 5.278.2. Initial and final graph of the same_modulo constraint

(a)

(b)

Signature

Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:

• Sources of the initial graph cannot become sinks of the final graph,

• Sinks of the initial graph cannot become sources of the final graph.

From the previous observations and since we use the PRODUCT arc generator on the collections VARIABLES1 and VARIABLES2, we have that the maximum number of sources and sinks of the final graph is respectively equal to |VARIABLES1| and |VARIABLES2|. Therefore we can rewrite NSOURCE=|VARIABLES1| to NSOURCE≥|VARIABLES1| and simplify NSOURCE to NSOURCE. In a similar way, we can rewrite NSINK=|VARIABLES2| to NSINK≥|VARIABLES2| and simplify NSINK to NSINK.