5.268. period

DESCRIPTIONLINKS
Origin

N.Β Beldiceanu

Constraint

πš™πšŽπš›πš’πš˜πš(π™Ώπ™΄πšπ™Έπ™Ύπ™³,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš)

Arguments
π™Ώπ™΄πšπ™Έπ™Ύπ™³πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™²πšƒπšπšŠπšπš˜πš–
Restrictions
π™Ώπ™΄πšπ™Έπ™Ύπ™³β‰₯1
π™Ώπ™΄πšπ™Έπ™Ύπ™³β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
π™²πšƒπšβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Let us note V 0 ,V 1 ,...,V m-1 the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. π™Ώπ™΄πšπ™Έπ™Ύπ™³ is the period of the sequence V 0 V 1 ...V m-1 according to constraint π™²πšƒπš . This means that π™Ώπ™΄πšπ™Έπ™Ύπ™³ is the smallest natural number such that V i π™²πšƒπš V i+π™Ώπ™΄πšπ™Έπ™Ύπ™³ holds for all i∈0,1,...,m-π™Ώπ™΄πšπ™Έπ™Ύπ™³-1.

Example
3,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-4,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-4,πšŸπšŠπš›-1,πšŸπšŠπš›-1,=

The πš™πšŽπš›πš’πš˜πš constraint holds since, as depicted by FigureΒ 5.268.1, its first argument π™Ώπ™΄πšπ™Έπ™Ύπ™³=3 is equal (i.e.,Β since π™²πšƒπš is set to =) to the period of the sequence 1 1 4 1 1 4 1 1.

Figure 5.268.1. A sequence that has a period of 3
ctrs/period1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be shifted.

  • All occurrences of two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped; all occurrences of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be renamed to any unused value.

Algorithm

When π™²πšƒπš corresponds to the equality constraint, a potentially incomplete filtering algorithm based on 13 deductions rules is described inΒ [BeldiceanuPoder04]. The generalisation of these rules to the case where π™²πšƒπš is not the equality constraint is discussed.

See also

implies: πš™πšŽπš›πš’πš˜πš_πšŽπš‘πšŒπšŽπš™πš_0.

soft variant: πš™πšŽπš›πš’πš˜πš_πšŽπš‘πšŒπšŽπš™πš_0Β (value 0 can match any other value).

Keywords

combinatorial object: periodic, sequence.

constraint type: predefined constraint, timetabling constraint, scheduling constraint.

filtering: border.