PartitionGenerator.cc

Go to the documentation of this file.

#include "CommonTools/Statistics/interface/PartitionGenerator.h"
#include <algorithm>
 
using namespace std;
 
vector<PartitionGenerator::Partition> PartitionGenerator::partitions(int collectionSize, int minCollectionSize) const {
  std::vector<Partition> partitions;
 
  // at the very least, we have a single bag of size 'collectionSize'
  partitions.push_back(Partition(1, collectionSize));
 
  int first = collectionSize - minCollectionSize, second = minCollectionSize;
  while (first >= second) {
    // try to further divide the first
    std::vector<Partition> subPartitions = this->partitions(first, second);
    std::vector<Partition>::iterator isub;
    for (isub = subPartitions.begin(); isub != subPartitions.end(); isub++) {
      const Partition& sub = *isub;
      // reject subPartitions of first with a last element smaller than second
      if (sub.back() < second)
        continue;
      Partition partition(sub.size() + 1);
      copy(sub.begin(), sub.end(), partition.begin());
      partition[partition.size() - 1] = second;
      partitions.push_back(partition);
    }
    first--;
    second++;
  }
 
  return partitions;
}
 
vector<std::vector<PartitionGenerator::Partition> > PartitionGenerator::sortedPartitions(int collectionSize,
                                                                                         int minCollectionSize) const {
  std::vector<Partition> partitions = this->partitions(collectionSize, minCollectionSize);
  sort(partitions.begin(), partitions.end(), LessCollections());
 
  std::vector<std::vector<Partition> > sortedPartitions;
  sortedPartitions.resize(partitions.rbegin()->size());
 
  for (std::vector<Partition>::const_iterator i = partitions.begin(); i != partitions.end(); i++) {
    sortedPartitions[(*i).size() - 1].push_back(*i);
  }
 
  return sortedPartitions;
}