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 #ifndef SUNDANCE_COMBINATORIALUTILS_H
00032 #define SUNDANCE_COMBINATORIALUTILS_H
00033
00034 #include "SundanceDefs.hpp"
00035 #include "Teuchos_Array.hpp"
00036 #include "SundanceMultiSet.hpp"
00037 #include "SundanceMap.hpp"
00038 #include "SundanceOrderedTuple.hpp"
00039
00040 namespace Sundance
00041 {
00042 using Teuchos::Array;
00043 class IntVec;
00044
00045
00046
00047
00048
00049
00050 Array<Array<int> > partitionInteger(int n);
00051
00052
00053
00054
00055 void weightedPartitions(int n, const Array<int>& w,
00056 Array<Array<int> >& parts);
00057
00058
00059 void weightedOrderedPartitions(const IntVec& v, const Array<int>& w,
00060 Array<Array<IntVec> >& parts);
00061
00062
00063
00064 void pSet(const IntVec& lambda, const IntVec& nu, int s,
00065 Array<Array<IntVec> >& K, Array<Array<IntVec> >& L);
00066
00067
00068
00069
00070 void restrictedCompositions(int n, int M, Array<Array<int> >& rComps);
00071
00072
00073 bool nextNum(Array<int>& digits, const Array<int>& radix);
00074
00075
00076
00077
00078
00079
00080 Array<Array<Array<int> > > compositions(int n);
00081
00082
00083
00084
00085
00086 Array<Array<int> > nonNegCompositions(int n, int J);
00087
00088
00089
00090
00091
00092
00093
00094 Array<Array<MultiSet<int> > > multisetCompositions(int s,
00095 const MultiSet<int>& x);
00096
00097
00098
00099
00100 Set<MultiSet<int> > multisetSubsets(const MultiSet<int>& x);
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116 Array<Array<MultiSet<int> > > multisetSubsetNTuples(int n,
00117 const MultiSet<int>& x);
00118
00119
00120
00121
00122
00123
00124 Array<Array<int> > distinctIndexTuples(int m, int n);
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135 Array<Array<int> > indexCombinations(const Array<int>& s);
00136
00137
00138 int pow2(int n);
00139
00140
00141
00142
00143 Array<int> bitsOfAnInteger(int x, int n);
00144
00145
00146
00147
00148
00149 template <class T>
00150 class Pair: public OrderedPair<T, T>
00151 {
00152 public:
00153 Pair(const T& a, const T& b)
00154 : OrderedPair<T, T>(a, b)
00155 {;}
00156 };
00157
00158 template <class T> inline
00159 std::ostream& operator<<(std::ostream& os, const Pair<T>& p)
00160 {
00161 os << "Pair(" << p.first() << ", " << p.second() << ")";
00162 return os;
00163 }
00164
00165
00166
00167
00168 template <class T>
00169 class SortedPair: public OrderedPair<T, T>
00170 {
00171 public:
00172 SortedPair(const T& a, const T& b)
00173 : OrderedPair<T, T>(std::min(a, b), std::max(a,b))
00174 {;}
00175 };
00176
00177 template <class T> inline
00178 std::ostream& operator<<(std::ostream& os, const SortedPair<T>& p)
00179 {
00180 os << "Pair(" << p.first() << ", " << p.second() << ")";
00181 return os;
00182 }
00183
00184
00185
00186
00187
00188
00189
00190 Set<Pair<MultiSet<int> > >
00191 loadPartitions(int x, int n,
00192 const MultiSet<int>& left,
00193 const MultiSet<int>& right);
00194
00195
00196
00197
00198
00199
00200 Set<Pair<MultiSet<int> > >
00201 binaryPartition(const MultiSet<int>& m);
00202
00203
00204
00205
00206
00207
00208 Set<MultiSet<MultiSet<int> > >
00209 multisetPartitions(const MultiSet<int>& m);
00210
00211
00212
00213
00214
00215 Map<int, int> countMap(const MultiSet<int>& m);
00216
00217
00218
00219 template <class T> inline
00220 Array<Array<Array<T> > > indexArrangements(const MultiSet<T>& mu,
00221 const Array<int>& k)
00222 {
00223 int nBins = k.size();
00224
00225 int M = 0;
00226 for (int i=0; i<nBins; i++)
00227 {
00228 M += k[i];
00229 }
00230
00231 Array<T> I;
00232 typename MultiSet<T>::const_iterator iter;
00233 for (iter=mu.begin(); iter!=mu.end(); iter++)
00234 {
00235 I.append(*iter);
00236 }
00237
00238 Array<Array<Array<T> > > rtn;
00239
00240 do
00241 {
00242 Array<Array<T> > bins(nBins);
00243 int count = 0;
00244 for (int i=0; i<nBins; i++)
00245 {
00246 for (int j=0; j<k[i]; j++)
00247 {
00248 bins[i].append(I[count++]);
00249 }
00250 }
00251 rtn.append(bins);
00252 }
00253 while (std::next_permutation(I.begin(), I.end()));
00254 return rtn;
00255 }
00256
00257
00258
00259
00260 template <class T> inline
00261 Array<Array<Array<T> > > binnings(const MultiSet<T>& mu, int n)
00262 {
00263 int N = mu.size();
00264 Array<Array<int> > c = compositions(N)[n-1];
00265 Array<Array<Array<T> > > rtn;
00266
00267 for (int i=0; i<c.size(); i++)
00268 {
00269 Array<Array<Array<T> > > a = indexArrangements(mu, c[i]);
00270 for (int j=0; j<a.size(); j++)
00271 {
00272 rtn.append(a[j]);
00273 }
00274 }
00275 return rtn;
00276 }
00277
00278
00279 inline int factorial(const MultiSet<int>& ms)
00280 {
00281 Sundance::Map<int, int> counts;
00282
00283 for (MultiSet<int>::const_iterator i=ms.begin(); i!=ms.end(); i++)
00284 {
00285 if (counts.containsKey(*i)) counts[*i]++;
00286 else counts.put(*i, 1);
00287 }
00288
00289 int rtn = 1;
00290 for (Sundance::Map<int, int>::const_iterator
00291 i=counts.begin(); i!=counts.end(); i++)
00292 {
00293 int f = 1;
00294 for (int j=1; j<=i->second; j++) f *= j;
00295 rtn *= f;
00296 }
00297 return rtn;
00298 }
00299
00300
00301 }
00302
00303
00304
00305 #endif
00306
00307
00308