Question

Show that Algorithm 1 produces the next larger permutation in lexicographic order.

Short answer

We have proved that the algorithm 1 produces the next larger permutation in lexicographic order.

Step-by-step solution

Definition of Concept

Permutations: A permutation of a set is a loosely defined arrangement of its members into a sequence or linear order, or, if the set is already ordered, a rearrangement of its elements, in mathematics. The act of changing the linear order of an ordered set is also referred to as "permutation."

Lexicographic order: The lexicographic or lexicographical order (also known as lexical order or dictionary order) in mathematics is a generalisation of the alphabetical order of dictionaries to sequences of ordered symbols or, more broadly, elements of a totally ordered set.

Show that Algorithm 1 produces the next larger permutation in lexicographic order 

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.