permutations.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * HUC - Hurna Core
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #ifndef MODULE_COMBINATORY_PERMUTATIONS_HXX
21 #define MODULE_COMBINATORY_PERMUTATIONS_HXX
22 
23 // STD includes
24 #include <list>
25 
26 namespace huc
27 {
28  namespace combinatory
29  {
43  template <typename Container, typename IT>
44  std::list<Container> Permutations(const IT& begin, const IT& end)
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  }
77  }
78 }
79 
80 #endif // MODULE_COMBINATORY_PERMUTATIONS_HXX
std::list< Container > Permutations(const IT &begin, const IT &end)