huc::combinatory Namespace Reference

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
Containertype of IT type.
ITtype 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.

46  {
47  std::list<Container> combinations;
48 
49  // Recusion termination
50  const auto kSeqSize = static_cast<const int>(std::distance(begin, end));
51  if (kSeqSize <= 0)
52  return combinations;
53 
54  // Keep first element
55  Container elementContainer;
56  elementContainer.push_back(*begin);
57  combinations.push_back(elementContainer);
58 
59  // Recursion termination
60  if (kSeqSize == 1)
61  return combinations;
62 
63  // Build all permutations of the suffix - Recursion
64  auto subCombinations = Combinations<Container, IT>(begin + 1, end);
65 
66  // Put the letter into every possible position of the existing permutations.
67  for (auto it = subCombinations.begin(); it != subCombinations.end(); ++it)
68  {
69  combinations.push_back(*it);
70  it->push_back(*begin);
71  combinations.push_back(*it);
72  }
73 
74  return combinations;
75  }
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
ITtype 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.

44  {
45  // Take the smallest sequence for initial count
46  const auto kFirstSize = std::distance(beginFirst, endFirst);
47  const auto kSecondSize = std::distance(beginSecond, endSecond);
48  const bool kIsFirstSmaller = (kFirstSize <= kSecondSize);
49 
50  // Create and set enough capacity for the intersection
51  Container intersection;
52  intersection.reserve((kIsFirstSmaller) ? kFirstSize : kSecondSize);
53 
54  // Count each element of the smaller array
55  std::multiset<typename std::iterator_traits<IT>::value_type> count;
56  const auto kCountEndIt = (kIsFirstSmaller) ? endFirst : endSecond;
57  for (auto it = (kIsFirstSmaller) ? beginFirst : beginSecond; it != kCountEndIt; ++it)
58  count.insert(*it);
59 
60  // Push the element if find into the multiset and delete its instance from the counter
61  auto kIntersectEndIt = (kIsFirstSmaller) ? endSecond : endFirst;
62  for (auto it = (kIsFirstSmaller) ? beginSecond : beginFirst; it != kIntersectEndIt; ++it)
63  {
64  // Move element from count to intersection if found
65  auto foundIt = count.find(*it);
66  if (foundIt != count.end())
67  {
68  intersection.push_back(*it);
69  count.erase(foundIt);
70  }
71  }
72 
73  return intersection;
74  }
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
ITtype 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.

43  {
44  // Lambda that count each element occurence within the map "count"
45  std::map<typename std::iterator_traits<IT>::value_type, int> count;
46  auto lCountElement = [&count](typename std::iterator_traits<IT>::value_type(val))
47  {
48  auto countIt = count.find(val);
49  if (countIt != count.end())
50  ++countIt->second;
51  else
52  count.emplace(val, 1);
53  };
54 
55  // Count both sequences
56  std::for_each(beginFirst, endFirst, lCountElement);
57  std::for_each(beginSecond, endSecond, lCountElement);
58 
59  // Decrease the count of each element given the full sequence
60  for (auto it = beginFull; it != endFull; ++it)
61  {
62  auto countIt = count.find(*it);
63  if (countIt == count.end())
64  return false;
65  if (--countIt->second < 0)
66  return false;
67  }
68 
69  // Fail if hte count is not equal to 0
70  for (auto it = count.begin(); it != count.end(); ++it)
71  if (it->second != 0)
72  return false;
73 
74  return true;
75  }
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
ITtype 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.

45  {
46  std::list<Container> permutations; // Contains the output permutations
47 
48  // Recusion termination - Empty sequence
49  const auto kSeqSize = static_cast<const int>(std::distance(begin, end));
50  if (kSeqSize <= 0)
51  return permutations;
52 
53  // Recusion termination - Unique element
54  if (kSeqSize == 1)
55  {
56  Container elementContainer;
57  elementContainer.push_back(*begin);
58  permutations.push_back(elementContainer);
59  return permutations;
60  }
61 
62  // Build all permutations of the suffix - Recursion
63  auto subPermutations = Permutations<Container, IT>(begin + 1, end);
64 
65  // Put the letter into every possible position of the existing permutations.
66  Container currentPermutation;
67  for (auto it = subPermutations.begin(); it != subPermutations.end(); ++it)
68  for (int i = 0; i < kSeqSize; ++i)
69  {
70  currentPermutation = *it;
71  currentPermutation.insert(currentPermutation.begin() + i, *begin);
72  permutations.push_back(currentPermutation);
73  }
74 
75  return permutations;
76  }