Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

binomial.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Guido Tack, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-25 10:59:56 +0100 (Fri, 25 Nov 2005) $ by $Author: tack $
00010  *     $Revision: 2640 $
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 #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    * Only half of the lower half of the matrix is represented, as only
00083    * binomial coefficients with m<=n are defined, and the lower triangle
00084    * is symmetric.
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 // STATISTICS: set-prop