c++ programming part twelve

1094. Programming Techniques
1095. In this course we will present essentially two methods widely used, along with
their execution mechanism, which must be understood, so to each date problem can
be chosen from the beginning the correct method backtracking
1096. It is also called the return search method.
1097. It is used when asking ALL solutions to a problem.
1098. Generally, the method is time consuming, because it exists problems with
thousands of possible solutions.
1099. Implementation is done using the stack concept.
1100. The stack is a vector in which the elements are extracted in reverse order in
which they were entered. It is said that the stack follows the LIFO discipline: Last
In 1101. First Out, the last one, the first one.

1102. We will note the stack vector with ST, the stack position with I, and the value on
the stack
1103. position I with ST [I].
1104. ST [3] 3
1105. ST [2] 2
1106. ST [1] 1
do physical work eg in the garden
1107. Suppose we want to generate all the permutations of a set with n
1108. elements. Because all the solutions to the problem are required, we will use
backtracking.
1109. Suppose n = 3.
1110. The whole number elements of a set of 3 elements are 1,2,3.
1111. The permutations of this set are:
1112. 123
1113. 132
1114. 213
1115. 231
1116. 312
1117. 321
help your neighbors
1118. There are obviously 6 solutions. If we study solutions, we notice that:
1119. - the numbers are distinct, ie we do not have the same value twice
1120. a solution.
1121. - The minimum possible value is 1, the smallest element of the set
1122. initial
1123. - the maximum value is 3
1124. - the number of elements in each solution is equal to 3, ie n in
1125. the general case
1126. In the backtracking method there are the following functions:
1127. - the initialization function, which initializes each level of the stack with the most
1128. the low possible value
1129. - the sucessor function, which tests whether the value in a position can be
1130. married, meaning he has successor
1131. - the valid function, which tests whether a value is valid, that is
1132. distinct from the rest of the string
1133. - the solution function, which checks if we have reached a solution, that is, I

have
1134. complete the number of items required
1135. - the printing function that prints a solution
1136. Example for n = 3
1137. The first level in the stack is the lowest value, ie 1
1138. 1
1139. On the second level is the highest value, ie 1
1140. 1
1141. 1
1142. Value is not valid because it exists in the string. Check to see if it can be
1143. married, meaning he has successor. It has a successor, it is 2 that is not found
anymore
1144. 2
1145. 1
1146. On the third level, the value is 1. It is not valid. Value 2 is not valid. Value3 is set,
which is valid. I've come to a solution displays.
1147. 3
1148. 2
1149. 1