38 using namespace Gecode;
56 int v0 = 5,
int q0 = 3,
int lambda0 = 2,
int d0 = 4)
58 _v(
"v",
"number of sequences", v0 ),
59 _q(
"q",
"number of symbols", q0 ),
60 _l(
"l",
"sets of symbols per sequence (lambda)", lambda0),
61 _d(
"d",
"Hamming distance between sequences", d0 ),
62 _permutation(
"permutation",
"use permutation constraints if d=4",
74 _permutation.
add(
true,
"full" );
75 _permutation.
add(
false,
"none");
77 _symmetry.add(
true,
"true" );
78 _symmetry.add(
false,
"false");
81 void parse(
int& argc,
char* argv[]) {
85 int v(
void)
const {
return _v.
value(); }
87 int q(
void)
const {
return _q.
value(); }
89 int l(
void)
const {
return _l.
value(); }
91 int d(
void)
const {
return _d.value(); }
96 bool symmetry(
void)
const {
return _symmetry.value(); }
134 nseqpair((
v*(
v-1))/2),
136 diff(*this,
n*nseqpair, 0, 1)
149 for (
int i =
v;
i--; )
156 for (
int a = 0;
a <
v; ++
a) {
157 for (
int b =
a+1;
b <
v; ++
b) {
158 for (
int i =
n;
i--; ) {
164 assert(nseqi == nseqpair);
169 for (
int i = nseqpair;
i--; ) {
175 if (
opt.symmetry()) {
178 for (
int r = 0;
r<
v-1; ++
r) {
182 for (
int c = 0;
c<
n-1; ++
c) {
188 for (
int c = 0;
c <
n; ++
c) {
198 if (
opt.permutation()) {
205 for (
int r1 = 0; r1 <
v; ++r1) {
206 for (
int r2 = r1+1; r2 <
v; ++r2) {
211 for (
int i =
d;
i--; ) perm[
i] =
IntVar(*
this, 0,
n-1);
213 IntVar cform(*
this, 0, 1);
219 for (
int i = 2*
d;
i--; ) _p[
i] =
IntVar(*
this, 1, q);
221 for (
int i = 0;
i < 2; ++
i) {
222 for (
int j = 0; j <
d; ++j) {
228 for (
int i = 0;
i <
d; ++
i) {
230 rel(*
this, cform*
d +
i == index);
231 IntVar value(*
this, 1, q);
232 element(*
this, _p, index, value);
233 element(*
this, row2, perm[
i], value);
246 for (
int i =
n;
i--; ) {
249 rel(*
this, (!p1b[
i] && !p2b[
i] && !p3b[
i] && !p4b[
i]) ==
250 (row1[
i] == row2[
i]));
259 rel(*
this, perm[0],
IRT_NQ, perm[2], cformb);
260 rel(*
this, perm[0],
IRT_NQ, perm[3], cformb);
261 rel(*
this, perm[1],
IRT_NQ, perm[2], cformb);
262 rel(*
this, perm[1],
IRT_NQ, perm[3], cformb);
268 rel(*
this, (!cformb) >> (perm[2] < perm[3]));
280 for (
int i = 0;
i <
v; ++
i) {
282 os <<
r << std::endl;
297 c.update(*
this, s.
c);
303 return new EFPA(*
this);
316 Script::run<EFPA,DFS,EFPAOptions>(
opt);
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Options for EFPA problems
int v(void) const
Get v, number of sequences.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
bool symmetry(void) const
Whether to use symmetry breaking.
int q(void) const
Get q, number of symbols.
int l(void) const
Get lambda, sets of symbols per sequence.
int d(void) const
Get d, Hamming distance between sequences.
EFPAOptions(const char *s, int v0=5, int q0=3, int lambda0=2, int d0=4)
Initialize options for example with name s.
bool permutation(void) const
Whether to use permutation constraints. Only active if d=4.
Example: Equidistant Frequency Permutation Arrays
int v
Number of sequences.
IntVarArray c
Variables for sequences.
int d
Hamming distance between any pair of sequences.
int main(int argc, char *argv[])
Main-function.
int nseqpair
Number of sequence pairs ( )
int n
Length of sequence ( )
EFPA(const EFPAOptions &opt)
Actual model.
int l
Number of sets of symbols for a sequence ( )
BoolVarArray diff
Differences between sequences.
virtual void print(std::ostream &os) const
Print instance and solution.
EFPA(EFPA &s)
Constructor for cloning s.
virtual Space * copy(void)
Copy during cloning.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Passing Boolean variables.
Boolean integer variables.
Parametric base-class for scripts.
String-valued option (integer value defined by strings)
void value(int v)
Set default value to v.
void add(int v, const char *o, const char *h=NULL)
Add option value for value v, string o, and help text h.
void value(unsigned int v)
Set default value to v.
Passing integer arguments.
Passing integer variables.
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Slice< A > row(int r) const
Access row r.
void ipl(IntPropLevel i)
Set default integer propagation level.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
IntRelType
Relation types for integers.
@ IRT_LQ
Less or equal ( )
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Multi _d(Gecode::IntArgs({3, 2, 1}))
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.