00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 #include <gecode/set.hh>
00042
00043 using namespace Gecode;
00044
00050 class HammingOptions : public Options {
00051 private:
00053 Driver::UnsignedIntOption _bits;
00055 Driver::UnsignedIntOption _distance;
00057 Driver::UnsignedIntOption _size;
00058
00059 public:
00061 HammingOptions(const char* s, unsigned int bits0,
00062 unsigned int distance0, unsigned int size0)
00063 : Options(s)
00064 , _bits("-bits","word size in bits",bits0)
00065 , _distance("-distance","minimum distance",distance0)
00066 , _size("-size","number of symbols",size0) {
00067 add(_bits);
00068 add(_distance);
00069 add(_size);
00070 }
00071
00073 unsigned int bits(void) const { return _bits.value(); }
00075 unsigned int distance(void) const { return _distance.value(); }
00077 unsigned int size(void) const { return _size.value(); }
00078
00079 };
00080
00092 class Hamming : public Script {
00093 private:
00095 SetVarArray xs;
00096 public:
00098 Hamming(const HammingOptions& opt) :
00099 xs(*this,opt.size(),IntSet::empty,1,opt.bits()) {
00100 SetVarArray cxs(*this,xs.size());
00101 for (int i=0; i<xs.size(); i++)
00102 rel(*this, xs[i], SRT_CMPL, cxs[i]);
00103
00104 for (int i=0; i<xs.size(); i++) {
00105 SetVar y = xs[i];
00106 SetVar cy = cxs[i];
00107 for (int j=i+1; j<xs.size(); j++) {
00108 SetVar x = xs[j];
00109 SetVar cx = cxs[j];
00110
00111 SetVar xIntCy(*this);
00112 SetVar yIntCx(*this);
00113
00114 rel(*this, x, SOT_INTER, cy, SRT_EQ, xIntCy);
00115 rel(*this, y, SOT_INTER, cx, SRT_EQ, yIntCx);
00116 IntVar xIntCyCard(*this,0,x.cardMax());
00117 IntVar yIntCxCard(*this,0,y.cardMax());
00118 cardinality(*this, xIntCy, xIntCyCard);
00119 cardinality(*this, yIntCx, yIntCxCard);
00120 post(*this, xIntCyCard+yIntCxCard >= opt.distance());
00121 }
00122 }
00123
00124 branch(*this, xs, SET_VAR_NONE, SET_VAL_MIN_INC);
00125 }
00126
00128 virtual void
00129 print(std::ostream& os) const {
00130 for (int i=0; i<xs.size(); i++) {
00131 os << "\t[" << i << "] = " << xs[i] << std::endl;
00132 }
00133 }
00134
00136 Hamming(bool share, Hamming& s) : Script(share,s) {
00137 xs.update(*this, share, s.xs);
00138 }
00140 virtual Space*
00141 copy(bool share) {
00142 return new Hamming(share,*this);
00143 }
00144
00145 };
00146
00150 int
00151 main(int argc, char* argv[]) {
00152 HammingOptions opt("Hamming",20,3,32);
00153 opt.parse(argc,argv);
00154 Script::run<Hamming,DFS,HammingOptions>(opt);
00155 return 0;
00156 }
00157
00158
00159
00160