CombinationGenerator< T > Class Template Reference

#include <CombinationGenerator.h>

Public Types
typedef std::vector< T >	Collection
typedef std::vector< Collection >	Combination
typedef std::vector< Combination >	VectorOfCombinations

Public Member Functions
std::vector< Combination >	combinations (const Collection &data, int numberOfCollections) const
std::vector< Combination >	combinations (const Collection &data, const PartitionGenerator::Partition &partition) const
std::vector< Combination >	combinations (const Collection &data) const

Private Member Functions
std::vector< Combination >	separateOneElement (const Collection &data) const
VectorOfCombinations	splitInTwoCollections (const Collection &data, int sizeFirst) const

Detailed Description

template<class T>
class CombinationGenerator< T >

Class to compute all distinct Combinations of a collection 'data' of objects of type 'T'. A Combination is a set of collections, each collection containing one or more objects, with any object in 'data' assigned to exactly one collection.

Definition at line 19 of file CombinationGenerator.h.

Member Typedef Documentation

template<class T >

typedef std::vector<T> CombinationGenerator< T >::Collection

Definition at line 23 of file CombinationGenerator.h.

template<class T >

typedef std::vector<Collection> CombinationGenerator< T >::Combination

Definition at line 25 of file CombinationGenerator.h.

template<class T >

typedef std::vector<Combination> CombinationGenerator< T >::VectorOfCombinations

Definition at line 26 of file CombinationGenerator.h.

Member Function Documentation

template<class T >

std::vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data, int  numberOfCollections  ) const

inline

Create combinations obtained by dividing 'data' according to all partitions with 'numberOfCollections' collections.

Definition at line 32 of file CombinationGenerator.h.

References begin, data, and PartitionGenerator::sortedPartitions().

Referenced by CombinationGenerator< T >::combinations(), CombinationGenerator< T >::separateOneElement(), and CombinationGenerator< T >::splitInTwoCollections().

  {
    std::vector<Combination> combinations;
    Collection sorted = data;

    // Sort if needed
    if (prev_permutation(sorted.begin(), sorted.end())) {
      sort(sorted.begin(), sorted.end());
    }

    // Create sorted partitions
    PartitionGenerator aPartitionGenerator;
    std::vector< std::vector<PartitionGenerator::Partition> > partitions 
      = aPartitionGenerator.sortedPartitions(data.size());
    
    // Use partitions of size 'numberOfCollections' only
    for (std::vector<PartitionGenerator::Partition>::const_iterator idiv 
       = partitions[numberOfCollections-1].begin(); 
     idiv != partitions[numberOfCollections-1].end(); idiv++) {

      const PartitionGenerator::Partition& partition = *idiv;
      std::vector<Combination> subCombinations 
    = this->combinations(data, partition);
      for ( typename std::vector<Combination>::const_iterator iComb 
         = subCombinations.begin(); 
       iComb != subCombinations.end(); iComb++) {
    combinations.push_back(*iComb);
      }
    }
    return combinations;
  }

template<class T >

std::vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data, const PartitionGenerator::Partition &  partition  ) const

inline

Create all combinations obtained by dividing 'data' according to Partition 'partition'.

Definition at line 69 of file CombinationGenerator.h.

References CombinationGenerator< T >::combinations(), data, gen::k, findQualityFiles::size, and CombinationGenerator< T >::splitInTwoCollections().

  {

    std::vector<Combination> combinations;

    // Check that sum of collection sizes in 'partition' 
    // amounts to number of elements in 'data' 
    int nElts = 0;
    for (PartitionGenerator::Partition::const_iterator iSize 
       = partition.begin(); iSize != partition.end(); iSize++) {
      nElts += *iSize;
    }
    if (nElts != data.size()) return combinations;

    Collection sortedData = data;
    // Sort if needed
    if (prev_permutation(sortedData.begin(), sortedData.end())) {
      sort(sortedData.begin(), sortedData.end());
    }

    // Create initial combination and put it on the stack
    Combination comb;
    comb.push_back(sortedData);
    if (partition.size() == 1) {
      // Return only one combination with only one collection
      combinations.push_back(comb);
      return combinations;
    }
    std::stack<Combination> cStack;
    cStack.push(comb);

    // Sort partitions by size 
    // Let 'sortedPartition' = ( n0, n1,... nk, nk+1,... nm ) 
    // Ordering is >= to speed up partitioning: n0 >= n1 >=... >= nm 
    PartitionGenerator::Partition sortedPartition = partition;
    sort(sortedPartition.begin(), sortedPartition.end(), std::greater_equal<int>());

    while (!cStack.empty()) {

      // 'combination' popped out of the stack 
      Combination combination = cStack.top(); cStack.pop();

      // At this stage 'combination' is made of collections 
      // of sizes ( n0+n1+...+nk, nk+1,... nm ) 
      // Now generate all combinations obtained by splitting 
      // the first collection of 'combination' in two, 
      // according to Partition 'biPartition' = (n0+n1+...+nk-1, nk) 
      int k = sortedPartition.size() - combination.size();
      int size = 0;
      for (int iColl = 0; iColl != k; iColl++) {
    size += sortedPartition[iColl];
      }
      PartitionGenerator::Partition biPartition(2);
      biPartition[0] = size; 
      biPartition[1] = sortedPartition[k];

      VectorOfCombinations subCombinations 
    = splitInTwoCollections(combination[0], biPartition[0]);
      for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
       iComb != subCombinations.end(); iComb++) { 

    // Check ordering of successive bins of equal size 
    if (combination.size() > 1) {
      if ((*iComb)[1].size() == combination[1].size()) {
        Collection adjBins;
        adjBins.push_back((*iComb)[1][0]);
        adjBins.push_back(combination[1][0]);
        // Drop 'combination' if successive bins of equal size not ordered 
        // i.e. if previous permutation exists 
        if (prev_permutation(adjBins.begin(), adjBins.end())) continue;
      }
    }

    // Append remaining collections of 'combination'
    Combination merged = *iComb;
    typename Combination::const_iterator it = combination.begin(); it++;
    for ( ; it != combination.end(); it++) { merged.push_back(*it); }

    // Store combination 'merged' if partitioning is complete, 
    // otherwise put it on the stack for further partitioning. 
    if (merged.size() == sortedPartition.size()) {
      combinations.push_back(merged);
    } else {
      cStack.push(merged);
    }
      }
    }
    return combinations;
  }

template<class T >

std::vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data ) const

inline

Create all combinations of elements from 'data'.

Definition at line 163 of file CombinationGenerator.h.

References CombinationGenerator< T >::combinations(), data, and PartitionGenerator::partitions().

  {

    std::vector<Combination> combinations;
    Collection sorted = data;
    // Sort if needed
    if (prev_permutation(sorted.begin(), sorted.end())) {
      sort(sorted.begin(), sorted.end());
    }

    PartitionGenerator aPartitionGenerator;
    std::vector<PartitionGenerator::Partition> partitions 
      = aPartitionGenerator.partitions(data.size());
    
    for (std::vector<PartitionGenerator::Partition>::const_iterator idiv 
       = partitions.begin(); idiv != partitions.end(); idiv++) {
      const PartitionGenerator::Partition& partition = *idiv;

      std::vector<Combination> subCombinations 
    = this->combinations(data, partition);
      for ( typename std::vector<Combination>::const_iterator iComb 
         = subCombinations.begin(); 
       iComb != subCombinations.end(); iComb++) {
    combinations.push_back(*iComb);
      }
    }
    return combinations;
  }

template<class T >

std::vector<Combination> CombinationGenerator< T >::separateOneElement ( const Collection &  data ) const

inlineprivate

Create all combinations obtained by dividing 'data' in two collections, the second one having only one element.

Definition at line 253 of file CombinationGenerator.h.

References coll, CombinationGenerator< T >::combinations(), i, j, and trackerHitRTTI::single.

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

  {
    std::vector<Combination> combinations;
    for ( typename Collection::const_iterator i = data.begin(); i != data.end(); i++) {
      Combination comb;
      Collection single; single.push_back(*i);
      Collection coll; 
      typename Collection::const_iterator j = data.begin();
      for ( ; j != i; j++) { coll.push_back(*j); }
      j++;
      for ( ; j != data.end(); j++) { coll.push_back(*j); }
      comb.push_back(coll); comb.push_back(single);
      combinations.push_back(comb);
    }
    return combinations;
  }

template<class T >

VectorOfCombinations CombinationGenerator< T >::splitInTwoCollections ( const Collection &  data, int  sizeFirst  ) const

inlineprivate

Create all combinations obtained by dividing 'data' in two collections, the first one being of size 'sizeFirst'

Definition at line 198 of file CombinationGenerator.h.

References mps_alisetup::collection, CombinationGenerator< T >::combinations(), edm::second(), CombinationGenerator< T >::separateOneElement(), and findQualityFiles::size.

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

  {
    std::vector<Combination> combinations;
    std::stack<Combination> cStack;

    // Create first combination with 2 partitions
    Combination comb; comb.push_back(data); comb.push_back(Collection());
    cStack.push(comb);

    while (!cStack.empty()) {
      Combination combination = cStack.top();
      cStack.pop();

      Collection collection = combination[0];
      std::vector<Combination> subCombinations = separateOneElement(collection);
      
      for ( typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
       iComb != subCombinations.end(); iComb++) {

    Collection second = combination[1];
    second.push_back((*iComb)[1][0]);

    // Abandon current combination if not ordered, 
    // i.e. if previous permutation exists 
    bool ordered = !prev_permutation(second.begin(), second.end());
    if (!ordered) continue;
    next_permutation(second.begin(), second.end());

    if ((*iComb)[0].size() == second.size()) {
      Collection adjBins;
      adjBins.push_back((*iComb)[0][0]);
      adjBins.push_back(second[0]);
      // Abandon current combination if successive bins of equal size 
      // not ordered, i.e. if previous permutation exists 
      if (prev_permutation(adjBins.begin(), adjBins.end())) continue;
    }

    Combination stored; 
    stored.push_back((*iComb)[0]);
    stored.push_back(second);

    if (stored[0].size() == sizeFirst) {
      combinations.push_back(stored);
    } else {
      cStack.push(stored);
    }
      }
    }
    return combinations;
  }