#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.

33 {}

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 roll_playback::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, roll_playback::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 run_regression::done, 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 asciidump::at, 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, roll_playback::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;
     }
 }