39 namespace Gecode {
namespace Int {
namespace Distinct {
48 const int MAX_MINC_FACTORS = 400;
49 extern const double mincFactors[MAX_MINC_FACTORS];
52 getMincFactor(
int domSize) {
53 return mincFactors[domSize - 1];
63 const int WIDTH_LIANG_BAI_FACTORS = 400;
64 extern const double liangBaiFactors[WIDTH_LIANG_BAI_FACTORS * WIDTH_LIANG_BAI_FACTORS];
67 getLiangBaiFactor(
int index,
int domSize) {
68 return liangBaiFactors[index*WIDTH_LIANG_BAI_FACTORS + domSize - 1];
85 ValToUpdate(
const ViewArray<View>&
x,
86 int minDomVal,
int maxDomVal, Region&
r);
92 double getMincUpdate(
int val,
unsigned int varSize)
const;
99 double getLiangUpdate(
int val,
unsigned int idx,
unsigned int varSize)
const;
104 ValToUpdate::ValToUpdate(
const ViewArray<View>&
x,
105 int minDomVal,
int maxDomVal, Region&
r)
106 : minVal(minDomVal) {
107 unsigned int width = maxDomVal - minDomVal + 1;
108 mincUpdate =
r.alloc<
double>(width);
109 std::fill(mincUpdate, mincUpdate + width, 1);
110 liangUpdate =
r.alloc<
double>(width);
111 std::fill(liangUpdate, liangUpdate + width, 1);
113 for (
int i=0;
i<
x.size();
i++) {
115 size_t s =
x[
i].size();
116 for (ViewValues<View> val(
x[
i]); val(); ++val) {
117 int idx = val.val() - minVal;
118 mincUpdate[idx] *= getMincFactor(s-1) / getMincFactor(s);
119 liangUpdate[idx] *= getLiangBaiFactor(
i, s-1) / getLiangBaiFactor(
i, s);
125 ValToUpdate::getMincUpdate(
int val,
unsigned int varSize)
const {
126 return mincUpdate[val-minVal] / getMincFactor(varSize-1);
130 ValToUpdate::getLiangUpdate(
int val,
unsigned int idx,
131 unsigned int varSize)
const {
132 return liangUpdate[val-minVal] / getLiangBaiFactor(idx, varSize-1);
137 void cbsdistinct(Space&,
unsigned int prop_id,
const ViewArray<View>&
x,
138 Propagator::SendMarginal send) {
147 for (
int i=0;
i<
x.size();
i++) {
148 unsigned int s =
x[
i].size();
149 if ((s >= MAX_MINC_FACTORS) || (s >= WIDTH_LIANG_BAI_FACTORS))
151 "Variable cardinality too big for using counting-based"
152 "search with distinct constraints");
153 ub.minc *= getMincFactor(s);
154 ub.liangBai *= getLiangBaiFactor(
i, s);
160 for (
const auto&
v :
x) {
161 if (
v.assigned())
continue;
169 ValToUpdate valToUpdate(
x, minVal, maxVal,
r);
173 double* solCounts =
r.alloc<
double>(maxVal - minVal + 1);
175 for (
int i=0;
i<
x.size();
i++) {
179 double normalization = 0;
181 for (ViewValues<View> val(
x[
i]); val(); ++val) {
184 unsigned int s =
x[
i].size();
188 localUB.minc *= valToUpdate.getMincUpdate(
v, s);
189 localUB.liangBai *= valToUpdate.getLiangUpdate(
v,
i, s);
192 double lowerUB =
std::min(localUB.minc, ::
sqrt(localUB.liangBai));
193 solCounts[val.val() - minVal] = lowerUB;
194 normalization += lowerUB;
199 for (ViewValues<View> val(
x[
i]); val(); ++val) {
207 x[
i].baseval(val.val()),
208 solCounts[val.val() - minVal] / normalization);
214 void cbssize(
const ViewArray<View>&
x, Propagator::InDecision in,
215 unsigned int&
size,
unsigned int& size_b) {
218 for (
const auto&
v :
x) {
Node * x
Pointer to corresponding Boolean expression node.
Exception: Base-class for exceptions
FloatVal sqrt(const FloatVal &x)
Return square root of x.
const FloatNum max
Largest allowed float value.
const FloatNum min
Smallest allowed float value.
bool assigned(View x, int v)
Whether x is assigned to value v.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})