binomial.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef __GECODE_SET_DISTINCT_BINOMIAL_ICC
00023 #define __GECODE_SET_DISTINCT_BINOMIAL_ICC
00024
00025 namespace Gecode { namespace Set { namespace Distinct {
00026
00030 class Binomial {
00031 private:
00033 Support::SharedArray<int> sar;
00035 unsigned int nmax;
00036
00044 unsigned int index(unsigned int i, unsigned int j);
00046 unsigned int y(unsigned int i, unsigned int j);
00048 void y(unsigned int i, unsigned int j, unsigned int c);
00050 GECODE_SET_EXPORT void init(unsigned int n);
00051
00052 public:
00054
00055
00056 Binomial(void);
00058 Binomial(const Binomial& b);
00060 Binomial(unsigned int nmax);
00062
00064
00065
00066 unsigned int c(unsigned int n, unsigned int m);
00068
00070
00071
00076 void update(bool share, Binomial& b);
00078 };
00079
00080
00081
00082
00083
00084
00085
00086
00087 forceinline unsigned int
00088 Binomial::index(unsigned int n, unsigned int m) {
00089 assert(n >= 4);
00090 assert(m >= 2);
00091 assert(m <= n/2);
00092 int n2 = (n-2)/2;
00093 int nn = n2*(n2-1);
00094 if (n % 2 == 1)
00095 nn += n2;
00096 return nn + m - 2;
00097 }
00098
00099 forceinline unsigned int
00100 Binomial::y(unsigned int n, unsigned int m) {
00101 if (n==m || m==0)
00102 return 1;
00103 if (m==1 || m==n-1)
00104 return n;
00105 if (m > (n/2))
00106 m = n-m;
00107
00108 return sar[ index(n,m) ];
00109 }
00110
00111 forceinline void
00112 Binomial::y(unsigned int n, unsigned int m, unsigned int c) {
00113 if (n==m || m==0) {
00114 assert(c==1);
00115 return;
00116 }
00117 if (m==1 || m==n-1) {
00118 assert(c==n);
00119 return;
00120 }
00121 if (m > (n/2)) {
00122 assert(c==y(n, n-m));
00123 return;
00124 }
00125
00126 sar[ index(n,m) ] = c;
00127 }
00128
00129 forceinline
00130 Binomial::Binomial(void) : sar(1), nmax(0) {
00131 init(10);
00132 }
00133
00134 forceinline
00135 Binomial::Binomial(const Binomial& b)
00136 : sar(b.sar), nmax(b.nmax) {}
00137
00138 forceinline
00139 Binomial::Binomial(unsigned int _nmax)
00140 : sar(1), nmax(0) {
00141 init(_nmax);
00142 }
00143
00144 forceinline unsigned int
00145 Binomial::c(unsigned int n, unsigned int m) {
00146 if (m>n)
00147 return 0;
00148 if (n>nmax)
00149 init(n);
00150 return y(n,m);
00151 }
00152
00153 forceinline void
00154 Binomial::update(bool share, Binomial& b) {
00155 nmax = b.nmax;
00156 sar.update(share, b.sar);
00157 }
00158 }}}
00159
00160 #endif
00161
00162