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 13 of file PartitionGenerator.h.

Member Typedef Documentation

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

Definition at line 17 of file PartitionGenerator.h.

Member Function Documentation

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

Return partitions in a row.

Definition at line 8 of file PartitionGenerator.cc.

References popcon2dropbox::copy(), plotBeamSpotDB::first, and edm::second().

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

      {

  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 = 1
	)		const

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

Definition at line 38 of file PartitionGenerator.cc.

References i.

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

                                                  {

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