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> SHA_Combinatory::Combinations	(	const IT &	begin,
		const IT &	end
	)

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

Complexity: O(2^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

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

Complexity: O(N + M).

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

Complexity: O(N + M + K).

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> SHA_Combinatory::Permutations	(	const IT &	begin,
		const IT &	end
	)

Permutations - Return all possible permutations of elements containing within the sequence.

Complexity: O(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