Functions
template<typename Container , typename IT >
std::list< Container >	Combinations (const IT &begin, const IT &end)

template<typename Container , typename IT >
Container	Intersection (const IT &beginFirst, const IT &endFirst, const IT &beginSecond, const IT &endSecond)

template<typename IT >
bool	IsInterleaved (const IT &beginFirst, const IT &endFirst, const IT &beginSecond, const IT &endSecond, const IT &beginFull, const IT &endFull)

template<typename Container , typename IT >
std::list< Container >	Permutations (const IT &begin, const IT &end)

Function Documentation

template<typename Container , typename IT >

std::list<Container> huc::combinatory::Combinations	(	const IT &	begin,
		const IT &	end
	)

Combinations - Return all possible combinations of elements containing within the sequence.

Remarks: a vector is not recommended as type for the Output_Container to avoid stack overflow as well as extra complexity due to frequent resizing (use instead structure such as list or a another with your own allocator).

Template Parameters

Container	type of IT type.
IT	type using to go through the collection.

Parameters

begin,end - iterators to the initial and final positions of the sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns: a collection containing all possible combined subsets.

Definition at line 45 of file combinations.hxx.

     {
       std::list<Container> combinations;
 
       // Recusion termination
       const auto kSeqSize = static_cast<const int>(std::distance(begin, end));
       if (kSeqSize <= 0)
         return combinations;
 
       // Keep first element
       Container elementContainer;
       elementContainer.push_back(*begin);
       combinations.push_back(elementContainer);
 
       // Recursion termination
       if (kSeqSize == 1)
         return combinations;
 
       // Build all permutations of the suffix - Recursion
       auto subCombinations = Combinations<Container, IT>(begin + 1, end);
 
       // Put the letter into every possible position of the existing permutations.
       for (auto it = subCombinations.begin(); it != subCombinations.end(); ++it)
       {
         combinations.push_back(*it);
         it->push_back(*begin);
         combinations.push_back(*it);
       }
 
       return combinations;
     }

template<typename Container , typename IT >

Container huc::combinatory::Intersection	(	const IT &	beginFirst,
		const IT &	endFirst,
		const IT &	beginSecond,
		const IT &	endSecond
	)

Intersection - Return Intersection of the two sequences.

Remarks: Retrieve the intersection of two sequences keeping dupplicate keys distinct.

Template Parameters

IT	type using to go through the collection.

Parameters

beginFirst,endFirst,beginSecond,endSecond - iterators to the initial and final positions of the sequences. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns: a vector containing the intersection of both sequences.

Definition at line 42 of file intersection.hxx.

     {
       // Take the smallest sequence for initial count
       const auto kFirstSize = std::distance(beginFirst, endFirst);
       const auto kSecondSize = std::distance(beginSecond, endSecond);
       const bool kIsFirstSmaller = (kFirstSize <= kSecondSize);
 
       // Create and set enough capacity for the intersection
       Container intersection;
       intersection.reserve((kIsFirstSmaller) ? kFirstSize : kSecondSize);
 
       // Count each element of the smaller array
       std::multiset<typename std::iterator_traits<IT>::value_type> count;
       const auto kCountEndIt = (kIsFirstSmaller) ? endFirst : endSecond;
       for (auto it = (kIsFirstSmaller) ? beginFirst : beginSecond; it != kCountEndIt; ++it)
           count.insert(*it);
 
       // Push the element if find into the multiset and delete its instance from the counter
       auto kIntersectEndIt = (kIsFirstSmaller) ? endSecond : endFirst;
       for (auto it = (kIsFirstSmaller) ? beginSecond : beginFirst; it != kIntersectEndIt; ++it)
       {
         // Move element from count to intersection if found
         auto foundIt = count.find(*it);
         if (foundIt != count.end())
         {
           intersection.push_back(*it);
           count.erase(foundIt);
         }
       }
 
       return intersection;
     }

template<typename IT >

bool huc::combinatory::IsInterleaved	(	const IT &	beginFirst,
		const IT &	endFirst,
		const IT &	beginSecond,
		const IT &	endSecond,
		const IT &	beginFull,
		const IT &	endFull
	)

IsInterleaved - Return whether or not if a sequence is the interleave of the two others.

Template Parameters

IT	type using to go through the collection.

Parameters

beginFirst,endFirst,beginSecond,endSecond,beginFull,endFull - iterators to the initial and final positions of the sequences. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns: true if the last sequence is the interleave of the two others, false otherwise.

Definition at line 40 of file is_interleaved.hxx.

     {
       // Lambda that count each element occurence within the map "count"
       std::map<typename std::iterator_traits<IT>::value_type, int> count;
       auto lCountElement = [&count](typename std::iterator_traits<IT>::value_type(val))
       {
         auto countIt = count.find(val);
         if (countIt != count.end())
           ++countIt->second;
         else
           count.emplace(val, 1);
       };
 
       // Count both sequences
       std::for_each(beginFirst, endFirst, lCountElement);
       std::for_each(beginSecond, endSecond, lCountElement);
 
       // Decrease the count of each element given the full sequence
       for (auto it = beginFull; it != endFull; ++it)
       {
         auto countIt = count.find(*it);
         if (countIt == count.end())
           return false;
         if (--countIt->second < 0)
           return false;
       }
 
       // Fail if hte count is not equal to 0
       for (auto it = count.begin(); it != count.end(); ++it)
         if (it->second != 0)
           return false;
 
       return true;
     }

template<typename Container , typename IT >

std::list<Container> huc::combinatory::Permutations	(	const IT &	begin,
		const IT &	end
	)

Permutations - Return all possible permutations of elements containing within the sequence (n!).

Remarks: a vector is not recommended as type for the Output_Container to avoid stack overflow as well as extra complexity due to frequent resizing (use instead structure such as list or a another with your own allocator).

Template Parameters

IT	type using to go through the collection.

Parameters

begin,end - iterators to the initial and final positions of the sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns: a collection containing all possible permuted sequences.

Definition at line 44 of file permutations.hxx.

     {
       std::list<Container> permutations; // Contains the output permutations
 
       // Recusion termination - Empty sequence
       const auto kSeqSize = static_cast<const int>(std::distance(begin, end));
       if (kSeqSize <= 0)
         return permutations;
 
       // Recusion termination - Unique element
       if (kSeqSize == 1)
       {
         Container elementContainer;
         elementContainer.push_back(*begin);
         permutations.push_back(elementContainer);
         return permutations;
       }
 
       // Build all permutations of the suffix - Recursion
       auto subPermutations = Permutations<Container, IT>(begin + 1, end);
 
       // Put the letter into every possible position of the existing permutations.
       Container currentPermutation;
       for (auto it = subPermutations.begin(); it != subPermutations.end(); ++it)
         for (int i = 0; i < kSeqSize; ++i)
         {
           currentPermutation = *it;
           currentPermutation.insert(currentPermutation.begin() + i, *begin);
           permutations.push_back(currentPermutation);
         }
 
       return permutations;
     }

Functions

Function Documentation