Statistics/src/PartitionGenerator.cc

0001 #include "CommonTools/Statistics/interface/PartitionGenerator.h"
0002 #include <algorithm>
0003
0004 using namespace std;
0005
0006 vector<PartitionGenerator::Partition> PartitionGenerator::partitions(int collectionSize, int minCollectionSize) const {
0007   std::vector<Partition> partitions;
0008
0009   // at the very least, we have a single bag of size 'collectionSize'
0010   partitions.push_back(Partition(1, collectionSize));
0011
0012   int first = collectionSize - minCollectionSize, second = minCollectionSize;
0013   while (first >= second) {
0014     // try to further divide the first
0015     std::vector<Partition> subPartitions = this->partitions(first, second);
0016     std::vector<Partition>::iterator isub;
0017     for (isub = subPartitions.begin(); isub != subPartitions.end(); isub++) {
0018       const Partition& sub = *isub;
0019       // reject subPartitions of first with a last element smaller than second
0020       if (sub.back() < second)
0021         continue;
0022       Partition partition(sub.size() + 1);
0023       copy(sub.begin(), sub.end(), partition.begin());
0024       partition[partition.size() - 1] = second;
0025       partitions.push_back(partition);
0026     }
0027     first--;
0028     second++;
0029   }
0030
0031   return partitions;
0032 }
0033
0034 vector<std::vector<PartitionGenerator::Partition> > PartitionGenerator::sortedPartitions(int collectionSize,
0035                                                                                          int minCollectionSize) const {
0036   std::vector<Partition> partitions = this->partitions(collectionSize, minCollectionSize);
0037   sort(partitions.begin(), partitions.end(), LessCollections());
0038
0039   std::vector<std::vector<Partition> > sortedPartitions;
0040   sortedPartitions.resize(partitions.rbegin()->size());
0041
0042   for (std::vector<Partition>::const_iterator i = partitions.begin(); i != partitions.end(); i++) {
0043     sortedPartitions[(*i).size() - 1].push_back(*i);
0044   }
0045
0046   return sortedPartitions;
0047 }