Combinatorics Class Reference

#include <Combinatorics.h>

Public Member Functions
	Combinatorics (Int_t Set, Int_t Subset)
Int_t	EqualPermutation (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Int_t	EqualPermutation_2_0 (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Int_t	EqualPermutation_2_2 (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Int_t	EqualPermutation_N_1 (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
std::vector< std::vector< UInt_t > >	GetCombinations ()
std::vector< std::vector< UInt_t > >	GetCombinations_2_0 ()
std::vector< std::vector< UInt_t > >	GetCombinations_2_2 ()
std::vector< std::vector< UInt_t > >	GetCombinations_N_1 ()
std::vector< std::vector< UInt_t > >	GetPermutations ()
void	Print (const std::vector< UInt_t > &permutation)
void	Print (const std::vector< std::vector< UInt_t > > &permutations)
virtual	~Combinatorics ()

Private Member Functions
Int_t	CalculatePermutations ()
void	initial_permutation (int size, int *permutation)
void	initial_subset (int k, int *subset)
Bool_t	next_permutation (int size, int *permutation)
Bool_t	next_subset (int n, int k, int *subset)
std::vector< UInt_t >	Rotate (const std::vector< UInt_t > &permutation, UInt_t digits)
void	Skip_2_0 (const std::vector< std::vector< UInt_t > > &permutation1, std::vector< std::vector< UInt_t > > &permutation2)
void	Skip_2_2 (const std::vector< std::vector< UInt_t > > &permutation1, std::vector< std::vector< UInt_t > > &permutation2)

Private Attributes
std::vector< std::vector< UInt_t > >	m_Combinations
std::vector< std::vector< UInt_t > >	m_Permutations
const Int_t	m_SetQuantity
std::vector< UInt_t >	m_Subset
const Int_t	m_SubsetQuantity

Detailed Description

Definition at line 17 of file Combinatorics.h.

Constructor & Destructor Documentation

Combinatorics::Combinatorics	(	Int_t	Set,
		Int_t	Subset
	)

Definition at line 19 of file Combinatorics.cc.

References CalculatePermutations().

                                                                    :

  m_SetQuantity(SetQuantity),
  m_SubsetQuantity(SubsetQuantity)
{
  // Get permutations
  CalculatePermutations();
}

Combinatorics::~Combinatorics ( )

virtual

Definition at line 32 of file Combinatorics.cc.

{}

Member Function Documentation

Int_t Combinatorics::CalculatePermutations ( )

private

Definition at line 47 of file Combinatorics.cc.

References i, initial_permutation(), initial_subset(), m_Permutations, m_SetQuantity, m_Subset, m_SubsetQuantity, next_permutation(), and next_subset().

Referenced by Combinatorics().

{
  if (m_SetQuantity < 1 || m_SubsetQuantity < 1 || (m_SetQuantity < m_SubsetQuantity)) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics] No valid choice of set or subset!" << endl;
      return -1;
    }
  
  Int_t* currentSubset = new Int_t[m_SubsetQuantity];
  Int_t* currentMapping = new Int_t[m_SetQuantity];

  initial_subset(m_SubsetQuantity, currentSubset);    
  do
    {
      initial_permutation(m_SetQuantity, currentMapping);        
      do
    {
      for (UShort_t i = 0; i < m_SubsetQuantity; i++) 
        {
              m_Subset.push_back(currentSubset[currentMapping[i]]);
        }
          m_Permutations.push_back(m_Subset);
          m_Subset.clear();
    }
      while (next_permutation(m_SubsetQuantity, currentMapping));
    }
  while (next_subset(m_SetQuantity, m_SubsetQuantity, currentSubset));

  delete[] currentSubset;
  delete[] currentMapping;

  return 0;
}

Int_t Combinatorics::EqualPermutation	(	const std::vector< UInt_t > &	permutation1,
		const std::vector< UInt_t > &	permutation2
	)

Definition at line 214 of file Combinatorics.cc.

References i.

Referenced by EqualPermutation_N_1(), and GetCombinations().

{
  if (p1.size() != p2.size())
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutation] permutations have different size!" << endl;
      return -1;
    }
  
  Float_t p1_sum = 0.0;
  Float_t p2_sum = 0.0;

  // Check whether permutations are equal (2^index)
  for (UInt_t i = 0; i < p1.size(); i++) p1_sum += (1 << p1.at(i));
  for (UInt_t i = 0; i < p2.size(); i++) p2_sum += (1 << p2.at(i));
  
  return (p1_sum == p2_sum ? 1 : 0);
}

Int_t Combinatorics::EqualPermutation_2_0	(	const std::vector< UInt_t > &	permutation1,
		const std::vector< UInt_t > &	permutation2
	)

Definition at line 351 of file Combinatorics.cc.

Referenced by Skip_2_0().

{
  if (p1.size() < 2) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutation_2_0] permutation has wrong size!" << endl;
      return -1;
    }
  
  // Check whether permutations are equal
  if ( ((1 << p1.at(0)) + (1 << p1.at(1)) == (1 << p2.at(0)) + (1 << p2.at(1)) ) &&
       p1.at(2) == p2.at(2) &&  p1.at(3) == p2.at(3) )
    {
      return 1;
    }
  return 0;
}

Int_t Combinatorics::EqualPermutation_2_2	(	const std::vector< UInt_t > &	permutation1,
		const std::vector< UInt_t > &	permutation2
	)

Definition at line 373 of file Combinatorics.cc.

Referenced by Skip_2_2().

{
  // Returns true if two permutations of four "int" are equal 
  // (equal means e.g.: 0123 = 1023 = 0132 = 1032)

  if (p1.size() != 4 && p2.size() != 4) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutationTwoByTwo] permutation(s) have wrong size!" << endl;
      return -1;
    }
  
  // Check whether permutations are equal (2^index)
  if ( ((1 << p1.at(0)) + (1 << p1.at(1)) == (1 << p2.at(0)) + (1 << p2.at(1)) ) && 
       ((1 << p1.at(2)) + (1 << p1.at(3)) == (1 << p2.at(2)) + (1 << p2.at(3)) ) ) 
    {
      return 1;
    }
  return 0;
}

Int_t Combinatorics::EqualPermutation_N_1	(	const std::vector< UInt_t > &	permutation1,
		const std::vector< UInt_t > &	permutation2
	)

Definition at line 398 of file Combinatorics.cc.

References EqualPermutation().

{
  // Returns true if two permutations of four "int" are equal 
  // (equal means e.g.: 012 = 102)

  if (p1.size() !=  p2.size()) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutationTwoByTwo] permutation(s) have wrong size!" << endl;
      return -1;
    }
  
  return (EqualPermutation(p1, p2) && p1.back() == p2.back() ? 1 : 0);
}

vector< vector< UInt_t > > Combinatorics::GetCombinations

(

)

Definition at line 189 of file Combinatorics.cc.

References EqualPermutation(), i, LogDebug, m_Combinations, and m_Permutations.

Referenced by Tau3MuReco::findCorrectPairing(), and GetCombinations_N_1().

{
  if (m_Permutations.size() == 0) 
    {
      LogDebug("Combinatorics") << "Nothing to do." << endl;
      return m_Combinations;
    }
  
  m_Combinations.push_back(m_Permutations.at(0));

  for (UInt_t i = 1; i < m_Permutations.size(); i++)
    {
      if (!EqualPermutation(m_Combinations.back(), m_Permutations.at(i))) 
        {
          m_Combinations.push_back(m_Permutations.at(i));
        }
    }
  return m_Combinations;
}

vector< vector< UInt_t > > Combinatorics::GetCombinations_2_0

(

)

Definition at line 270 of file Combinatorics.cc.

References LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_0().

{
  // combination vector returned
  vector< vector <UInt_t> > FinalCombinations; 

  if (m_Permutations.size() == 0) 
    {
      LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Nothing to do." << endl;
      return FinalCombinations;
    }
  
  // So far only for subsets of four indices
  if (m_SubsetQuantity != 4) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Subset must be 4." << endl;
      return FinalCombinations;
    }

  // Skip specific permutations
  Skip_2_0(m_Permutations, FinalCombinations);

  return FinalCombinations;
}

vector< vector< UInt_t > > Combinatorics::GetCombinations_2_2

(

)

Definition at line 239 of file Combinatorics.cc.

References LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_2().

{
  // combination vector returned
  vector< vector <UInt_t> > FinalCombinations; 

  if (m_Permutations.size() == 0) 
    {
      LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Nothing to do." << endl;
      return FinalCombinations;
    }
  
  // So far only for subsets of four indices
  if (m_SubsetQuantity != 4) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Subset must be 4." << endl;
      return FinalCombinations;
    }

  // Skip specific permutations
  Skip_2_2(m_Permutations, FinalCombinations);

  return FinalCombinations;
}

vector< vector< UInt_t > > Combinatorics::GetCombinations_N_1

(

)

Definition at line 416 of file Combinatorics.cc.

References GetCombinations(), i, j, LogDebug, m_Combinations, and Rotate().

{
  // Get combinations 
  m_Combinations.clear();
  GetCombinations();
  
  // combination vector returned
  vector < vector <UInt_t> > FinalCombinations;

  if (m_Combinations.size() == 0) 
    {
      LogDebug("Combinatorics") << "[Combinatorics::GetCombinationsThreeByOne] Nothing to do." << endl;
      return FinalCombinations;
    }
  
  for (UInt_t i = 0; i < m_Combinations.size(); i++)
    {
      vector <UInt_t> RotatingPermutation = m_Combinations.at(i);
      FinalCombinations.push_back(m_Combinations.at(i));

      for (UInt_t j = 1; j < RotatingPermutation.size(); j++)
        {
          FinalCombinations.push_back(Rotate(RotatingPermutation,j));
        }
    }
  return FinalCombinations;
}

vector< vector< UInt_t > > Combinatorics::GetPermutations

(

)

Definition at line 39 of file Combinatorics.cc.

References m_Permutations.

{
  return m_Permutations;
}

void Combinatorics::initial_permutation ( int  size, int *  permutation  )

private

Definition at line 85 of file Combinatorics.cc.

References i, and findQualityFiles::size.

Referenced by CalculatePermutations().

{
  for (int i = 0; i < size; i++) 
    {
      permutation[i] = i;
    }
}

void Combinatorics::initial_subset ( int  k, int *  subset  )

private

Definition at line 97 of file Combinatorics.cc.

References i, and gen::k.

Referenced by CalculatePermutations().

{
  for (int i = 0; i < k; i++) 
    {
      subset[i] = i;
    }
}

Bool_t Combinatorics::next_permutation ( int  size, int *  permutation  )

private

Definition at line 109 of file Combinatorics.cc.

References i, j, gen::k, findQualityFiles::size, and tmp.

Referenced by CalculatePermutations().

{
  int i, j, k;
  if (size < 2) return false;
  i = size - 2;
  
  while ((permutation[i] > permutation[i+1]) && (i != 0)) 
    {
      i--;
    }
  if ((i == 0) && (permutation[0] > permutation[1])) return false;
  
  k = i + 1;
  for (j = i + 2; j < size; j++ ) 
    {
      if ((permutation[j] > permutation[i]) && (permutation[j] < permutation[k])) 
    {
      k = j;
        }
    }
  
  // swap i and k 
  {
    int tmp = permutation[i];
    permutation[i] = permutation[k];
    permutation[k] = tmp;
  }
  
  for (j = i + 1; j <= ((size + i) / 2); j++) 
    {
      int tmp = permutation[j];
      permutation[j] = permutation[size + i - j];
      permutation[size + i - j] = tmp;
    }

  // return whether a next permutation exists
  return true;
}

Bool_t Combinatorics::next_subset ( int  n, int  k, int *  subset  )

private

Definition at line 155 of file Combinatorics.cc.

References i, and j.

Referenced by CalculatePermutations().

{
  int i;
  int j;
  int jsave;
  bool done;
  
  if ( subset[0] < n-k )
    {
      done = false;
      jsave = k-1;
      for ( j = 0; j < k-1; j++ )
        {
      if ( subset[j] + 1 < subset[j+1] )
            {
          jsave = j;
          break;
            }
        }
      for ( i = 0; i < jsave; i++ ) subset[i] = i;
      subset[jsave] = subset[jsave] + 1;
    }
  else
    {
      done = true;
    }
  // return whether a next subset exists
  return !done;
}

void Combinatorics::Print

(

const std::vector< UInt_t > &

permutation

)

Definition at line 476 of file Combinatorics.cc.

References i, and LogDebug.

{
  // Print permutations
  for (UShort_t i = 0; i < p.size(); i++)
    {
      LogDebug("Combinatorics") << (p.at(i));
    }
  LogDebug("Combinatorics") << endl;
}

void Combinatorics::Print

(

const std::vector< std::vector< UInt_t > > &

permutations

)

Definition at line 490 of file Combinatorics.cc.

References i, j, LogDebug, AlCaHLTBitMon_ParallelJobs::p, and findQualityFiles::size.

{
  LogDebug("Combinatorics") << "**************" << endl;
  LogDebug("Combinatorics") << "Permutations: " << p.size() << endl;

  // Print permutations
  for (UShort_t i = 0; i < p.size(); i++)
    {
      for(UShort_t j = 0; j < (p.at(0)).size(); j++) LogDebug("Combinatorics") << (p.at(i)).at(j);
      LogDebug("Combinatorics") << endl;
    }
}

vector< UInt_t > Combinatorics::Rotate ( const std::vector< UInt_t > &  permutation, UInt_t  digits  )

private

Definition at line 448 of file Combinatorics.cc.

References i, j, gen::k, AlCaHLTBitMon_ParallelJobs::p, and tmp.

Referenced by GetCombinations_N_1().

{
  vector<UInt_t> p;
  vector<UInt_t> tmp;
  
  if (permutation.size() <= digm_) 
    {
      edm::LogWarning("Combinatorics") << "[Combinatorics::Rotate] WARNING: More rotations than digm_ in permutation!" << endl;   
    }

  // Save the first i digm_
  for (UInt_t i = 0; i < digm_; i++) 
    {
      tmp.push_back(permutation.at(i));
    }
  for (UInt_t j = 0; j < permutation.size() - digm_; j++)
    {
      p.push_back(permutation.at(j + digm_));
    }
  for (UInt_t k = 0; k < digm_; k++) p.push_back(tmp.at(k));

  return p;
}

void Combinatorics::Skip_2_0 ( const std::vector< std::vector< UInt_t > > &  permutation1, std::vector< std::vector< UInt_t > > &  permutation2  )

private

Definition at line 298 of file Combinatorics.cc.

References EqualPermutation_2_0(), i, j, p1, and p2.

Referenced by GetCombinations_2_0().

{
  Bool_t Skip = kFALSE;

  p2.push_back(p1.at(0));
  
  for (UShort_t i = 1; i < p1.size(); i++)
    {
      for (UShort_t j = 0; j < p2.size(); j++)
        {
          if (EqualPermutation_2_0(p1.at(i), p2.at(j))) 
            {
              Skip = kTRUE;
            }
        }
      if (!Skip) p2.push_back(p1.at(i));

      Skip = kFALSE;
    }
}

void Combinatorics::Skip_2_2 ( const std::vector< std::vector< UInt_t > > &  permutation1, std::vector< std::vector< UInt_t > > &  permutation2  )

private

Definition at line 324 of file Combinatorics.cc.

References EqualPermutation_2_2(), i, j, p1, and p2.

Referenced by GetCombinations_2_2().

{
  Bool_t Skip = kFALSE;

  p2.push_back(p1.at(0));
  
  for (UShort_t i = 1; i < p1.size(); i++)
    {
      for (UShort_t j = 0; j < p2.size(); j++)
        {
          if (EqualPermutation_2_2(p1.at(i), p2.at(j))) 
            {
              Skip = kTRUE;
            }
        }
      if (!Skip) p2.push_back(p1.at(i));

      Skip = kFALSE;
    }
}

Member Data Documentation

std::vector<std::vector <UInt_t> > Combinatorics::m_Combinations

private

Definition at line 64 of file Combinatorics.h.

Referenced by GetCombinations(), and GetCombinations_N_1().

std::vector<std::vector <UInt_t> > Combinatorics::m_Permutations

private

Definition at line 63 of file Combinatorics.h.

Referenced by CalculatePermutations(), GetCombinations(), GetCombinations_2_0(), GetCombinations_2_2(), and GetPermutations().

const Int_t Combinatorics::m_SetQuantity

private

Definition at line 59 of file Combinatorics.h.

Referenced by CalculatePermutations().

std::vector<UInt_t> Combinatorics::m_Subset

private

Definition at line 62 of file Combinatorics.h.

Referenced by CalculatePermutations().

const Int_t Combinatorics::m_SubsetQuantity

private

Definition at line 60 of file Combinatorics.h.

Referenced by CalculatePermutations(), GetCombinations_2_0(), and GetCombinations_2_2().