4.1 Various Constraints over Lists and Arrays
The libraries
ic_global
and
ic_global_gac
implement a number of constraints over lists of integer variables.
They are loaded using a directive like
:- use_module(library(ic_global)). % or :- lib(ic_global).
For details of the implemented constraints, refer to the Reference Manual
for the libraries.
These constraints are commonly known as global constraints,
which simply indicates that they can constrain a large number of variables
at once, without breaking up the constraint into more primitive constraints.
This can on one hand facilitate problem modelling, and on the other hand
lead to more effective constraint propagation.
Note that some constraints are implemented in both of the libraries:
in these cases, ic_global_gac implements a "globally arc consistent"
version, while ic_global implements a less computationally expensive
version with weaker propagation.
Among the constraints provided are the following (refer to the
Reference Manual for the complete list):
-
alldifferent(+List)
-
A version of alldifferent/1 with strong propagation. - alldifferent(+List, ++Capacity)
-
Like alldifferent/1, but every value may occur Capacity times. - alldifferent_matrix(+Matrix)
-
Constrains the rows and columns of Matrix to be different values. - gcc(++Bounds,+Vars)
-
The global cardinality constraint makes sure certain values
occur with a certain frequency in Vars. This is a generalisation of the
occurrences-constraint.
See also gcc_matrix/3. - inverse(+Succ, +Pred)
-
Constrains elements of Succ to be the successors and Pred to be the
predecessors of nodes in a digraph. - lex_le(+List1, +List2)
-
Imposes a lexicographic ordering between the two lists. - lex_lt(+List1, +List2)
-
Imposes a strict lexicographic ordering between the two lists. - ordered(++Relation, +List)
-
Constrains List to be ordered according to Relation.
Relation is one of the atoms <, =<, >, >=, = . - ordered_sum(++List, +Sum)
-
The list elements are ordered and their sum is Sum. A combination of
ordered and sum constraint with stronger propagation. - occurrences(++Value, +List, ?N)
-
The value Value occurs in List N times.
Operationally: N gets updated to reflect the number of
possible occurrences in the List. List elements may get
instantiated to Value, or Value may be removed from their
domain if required by N. - same(+List1, +List2)
-
List2 is a permutation of List1. - sequence(+Low, +High, +K, +Vars, ++Values)
-
Every subsequence of Vars of length K contains at least Low and at most High
occurrences of Values.
Also sequence/4. - sorted(?List, ?Sorted)
-
Sorted is a sorted permutation of List. - sorted(?List, ?Sorted, ?Positions)
-
Sorted is a sorted permutation of List and Positions is a list whose
elements indicating the position of each unsorted list element within
the sorted list. - sumlist(+List, ?Sum)
-
The sum of the list elements is Sum. This constraint
is more efficient than a general IC sum constraint
if the list is long and Sum is not constrained frequently.