/data/refman/pasoursint/CMSSW_5_3_0/src/CommonTools/Statistics/interface/CombinationGenerator.h

Go to the documentation of this file.

#ifndef _CombinationGenerator_H_
#define _CombinationGenerator_H_

#include "CommonTools/Statistics/interface/PartitionGenerator.h"
#include <vector>
#include <stack>
#include <algorithm>
#include <functional>

template<class T>
class CombinationGenerator {

public:

  typedef std::vector<T> Collection;

  typedef std::vector<Collection> Combination;
  typedef std::vector<Combination> VectorOfCombinations;

  std::vector<Combination> 
  combinations(const Collection & data, int numberOfCollections) const 
  {
    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;
  }


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

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


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

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


private:

  VectorOfCombinations splitInTwoCollections(const Collection & data, 
                                            int sizeFirst) const
  {
    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;
  }

  std::vector<Combination> separateOneElement(const Collection & data) const
  {
    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;
  }

};

#endif