Statistics/interface/PartitionGenerator.h

0001 #ifndef _PartitionGenerator_H_
0002 #define _PartitionGenerator_H_
0003
0004 #include <vector>
0005
0006 /** Class to compute the possible partitions of a collection of
0007  *  'collectionSize' elements. A Partition is a list of
0008  *  subcollection sizes that add up to 'collectionSize',
0009  *  ordered in decreasing order of subcollection size.
0010  *  No subcollection size is less than 'minCollectionSize'.
0011  */
0012 class PartitionGenerator {
0013 public:
0014   typedef std::vector<int> Partition;
0015
0016   /** Return partitions in a row.
0017    */
0018   std::vector<Partition> partitions(int collectionSize, int minCollectionSize = 1) const;
0019
0020   /** Return partitions ordered according to the number of
0021    *  subcollections they have.
0022    *  'sortedPartitions[N]' = list of partitions with N subcollections.
0023    */
0024   std::vector<std::vector<Partition> > sortedPartitions(int collectionSize, int minCollectionSize = 1) const;
0025
0026 private:
0027   /** a private class just defining the () operator */
0028   class LessCollections {
0029   public:
0030     bool operator()(const Partition& a, const Partition& b) { return a.size() < b.size(); }
0031   };
0032 };
0033
0034 #endif