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