PartitionGenerator Class Reference

#include <PartitionGenerator.h>

List of all members.

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 filterCSVwithJSON::copy, 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, and python::multivaluedict::sort().

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