PartitionGenerator Class Reference

#include <PartitionGenerator.h>

Classes
class	LessCollections

Public Types
typedef std::vector< int >	Partition

Public Member Functions
std::vector< Partition >	partitions (int collectionSize, int minCollectionSize=1) const
std::vector< std::vector< Partition > >	sortedPartitions (int collectionSize, int minCollectionSize=1) const

Detailed Description

Class to compute the possible partitions of a collection of 'collectionSize' elements. A Partition is a list of subcollection sizes that add up to 'collectionSize', ordered in decreasing order of subcollection size. No subcollection size is less than 'minCollectionSize'.

Definition at line 12 of file PartitionGenerator.h.

Member Typedef Documentation

Partition

typedef std::vector<int> PartitionGenerator::Partition

Definition at line 14 of file PartitionGenerator.h.

Member Function Documentation

partitions()

vector< PartitionGenerator::Partition > PartitionGenerator::partitions	(	int	collectionSize,
		int	minCollectionSize = 1
	)		const

Return partitions in a row.

Definition at line 6 of file PartitionGenerator.cc.

                                                                                                                  {
  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;
}

References filterCSVwithJSON::copy, dqmdumpme::first, and edm::second().

Referenced by CombinationGenerator< T >::combinations().

sortedPartitions()

vector< std::vector< PartitionGenerator::Partition > > PartitionGenerator::sortedPartitions	(	int	collectionSize,
		int	minCollectionSize = 1
	)		const

Return partitions ordered according to the number of subcollections they have. 'sortedPartitions[N]' = list of partitions with N subcollections.

Definition at line 34 of file PartitionGenerator.cc.

                                                                                                                      {
  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;
}

References mps_fire::i.

Referenced by CombinationGenerator< T >::combinations().