Considering the given information:
Algorithm 1
L 1= Procedure 1 next permutation
\(\left( {{{\rm{a}}_{\rm{1}}}{\rm{,}}{{\rm{a}}_{\rm{2}}}{\rm{ \ldots \ldots \ldots }}..{{\rm{a}}_{\rm{n}}}{\rm{:}}} \right.\)Permutation of\({\rm{\{ 1,2, \ldots }}..{\rm{n\} }}\)not equal to\(\left. {{\rm{n,n - 1 \ldots \ldots 2,1}}} \right)\).
\({{\rm{L}}_{\rm{2}}}{\rm{:J = n - 1}}\)
\({{\rm{L}}_{\rm{3}}}{\rm{:}}\)while\({{\rm{a}}_{\rm{J}}}{\rm{ > }}{{\rm{a}}_{\rm{J}}}{\rm{ + 1}}\)
\({{\rm{L}}_{\rm{4}}}{\rm{:J = J - 1}}\)
\(\left\{ {\rm{J}} \right.\)Is the largest subscript with\(\left. {{{\rm{a}}_{\rm{J}}}{\rm{ < }}{{\rm{a}}_{\rm{J}}}{\rm{ + 1}}} \right\}\)
\({{\rm{L}}_{\rm{5}}}{\rm{:k = k - 1}}\)
\(\left\{ {{{\rm{a}}_{\rm{k}}}} \right.\)Is the smallest integer greater than\({{\rm{a}}_{\rm{J}}}\)to the right of\(\left. {{{\rm{a}}_{\rm{J}}}} \right\}\)
\({{\rm{L}}_{\rm{6}}}\): Interchange\({{\rm{a}}_{\rm{J}}}\)and\({{\rm{a}}_{\rm{x}}}\)
\({{\rm{L}}_{\rm{7}}}{\rm{:r = n}}\)
\({{\rm{L}}_{\rm{8}}}{\rm{:s = J + 1}}\)
\({{\rm{L}}_{\rm{9}}}\): while\({\rm{r > s}}\)
\({{\rm{L}}_{{\rm{10}}}}\): Begin.
\({{\rm{L}}_{{\rm{11}}}}\): Interchange\({{\rm{a}}_{\rm{r}}}\) and\({{\rm{a}}_{\rm{s}}}\)
\(\begin{array}{l}{{\rm{L}}_{{\rm{12}}}}{\rm{:r = r - 1}}\\{{\rm{L}}_{{\rm{13}}}}{\rm{:s = s + 1}}\\{{\rm{L}}_{{\rm{14}}}}{\rm{: end}}\end{array}\)
Using the following concept:
The largest permutation formed with \({\rm{1,2,3 \ldots \ldots }}..{\rm{n}}\) is\({\rm{n,n - 1,n - 2, \ldots }}..{\rm{2,1}}\).
Since, the largest permutation formed with\({\rm{1,2,3 \ldots \ldots }}..{\rm{n}}\)is\({\rm{n,n - 1,n - 2, \ldots }}..{\rm{2,1}}\).
So, if at all the given permutation is\({\rm{n,n - 1,n - 2, \ldots }}..{\rm{2,1}}\)the given algorithm is gainful. That is the reason in line 1 restrict that given permutation 10 not this. So, line 3 says that if\({{\rm{a}}_{\rm{J}}}{\rm{ > }}{{\rm{a}}_{{\rm{j + 1}}}}\) magnitude wise, then their position will be interchanged to give a larger value then the existing value.
For instance 41 is large than 14 while\({{\rm{a}}_{\rm{J}}}{{\rm{a}}_{{\rm{J + 1}}}}{\rm{ = 14}}\).
The digits are exchanged in the immediate and overall positions, as claimed in\({{\rm{L}}_{\rm{5}}}{\rm{ < }}{{\rm{L}}_{{\rm{11}}}}\).
Furthermore,\({{\rm{L}}_{{\rm{11}}}}\) is a comparison of\({{\rm{L}}_{\rm{3}}}{\rm{\& }}{{\rm{L}}_{\rm{6}}}\) to confirm that the immediate bigger comparison is among the available bigger compositions.
When\({{\rm{L}}_{{\rm{11}}}}\) is not present. The loop is traversed by the comparison process until the largest permutation in terms of magnitude occurs.
As a result, the provided algorithm is useful for determining the next larger permutation to the given permutation.
Hence proved, the Algorithm 1 produces the next larger permutation in lexicographic order.
