binomial.icc

00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Guido Tack, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-07-11 12:00:17 +0200 (Tue, 11 Jul 2006) $ by $Author: schulte $
00010  *     $Revision: 3344 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Set { namespace Distinct {
00023 
00027   class Binomial {
00028   private:
00030     Support::SharedArray<int> sar;
00032     unsigned int nmax;
00033     
00041     unsigned int index(unsigned int i, unsigned int j);
00043     unsigned int y(unsigned int i, unsigned int j);
00045     void y(unsigned int i, unsigned int j, unsigned int c);
00047     GECODE_SET_EXPORT void init(unsigned int n);
00048     
00049   public:
00051 
00052 
00053     Binomial(void);
00055     Binomial(const Binomial& b);
00057     Binomial(unsigned int nmax);
00059     
00061 
00062 
00063     unsigned int c(unsigned int n, unsigned int m);
00065 
00067 
00068 
00073     void update(bool share, Binomial& b);
00075   };
00076   
00077 
00078   /*
00079    * Only half of the lower half of the matrix is represented, as only
00080    * binomial coefficients with m<=n are defined, and the lower triangle
00081    * is symmetric.
00082    *
00083    */
00084   forceinline unsigned int
00085   Binomial::index(unsigned int n, unsigned int m) {
00086     assert(n >= 4);
00087     assert(m >= 2);
00088     assert(m <= n/2);
00089     int n2 = (n-2)/2;
00090     int nn = n2*(n2-1);
00091     if (n % 2 == 1)
00092       nn += n2;
00093     return nn + m - 2;
00094   }
00095 
00096   forceinline unsigned int
00097   Binomial::y(unsigned int n, unsigned int m) {
00098     if (n==m || m==0)
00099       return 1;
00100     if (m==1 || m==n-1)
00101       return n;
00102     if (m > (n/2))
00103       m = n-m;
00104 
00105     return sar[ index(n,m) ];
00106   }
00107 
00108   forceinline void
00109   Binomial::y(unsigned int n, unsigned int m, unsigned int c) {
00110     if (n==m || m==0) {
00111       assert(c==1);
00112       return;
00113     }
00114     if (m==1 || m==n-1) {
00115       assert(c==n);
00116       return;
00117     }
00118     if (m > (n/2)) {
00119       assert(c==y(n, n-m));
00120       return;
00121     }
00122 
00123     sar[ index(n,m) ] = c;
00124   }
00125 
00126   forceinline
00127   Binomial::Binomial(void) : sar(1), nmax(0) {
00128     init(10);
00129   }
00130   
00131   forceinline
00132   Binomial::Binomial(const Binomial& b)
00133     : sar(b.sar), nmax(b.nmax) {}
00134   
00135   forceinline
00136   Binomial::Binomial(unsigned int _nmax)
00137     : sar(1), nmax(0) {
00138     init(_nmax);
00139   }
00140 
00141   forceinline unsigned int
00142   Binomial::c(unsigned int n, unsigned int m) {
00143     if (m>n)
00144       return 0;
00145     if (n>nmax)
00146       init(n);
00147     return y(n,m);
00148   }
00149 
00150   forceinline void
00151   Binomial::update(bool share, Binomial& b) {
00152     nmax = b.nmax;
00153     sar.update(share, b.sar);
00154   }
00155 }}}
00156 
00157 // STATISTICS: set-prop