As an exercise list the 5! = 120 permutations of {1, 2, 3, 4, 5} in lexicographi
ID: 3829393 • Letter: A
Question
As an exercise list the 5! = 120 permutations of {1, 2, 3, 4, 5} in lexicographic order. After finishing this long exercise, you will see the need for an algorithm that systematically produces all permutations of a finite set. We will represent a permutation (a_1, a_2, a_3, ..., a_n) by an array A[] of length n+1, where A[j] = a_j for 1 lessthanorequalto k lessthanorequalto n, and the element A[0] is simply not used. Your program will include a function with the following heading. static void nextPermutation(int[] A){.. .} This method will alter its argument A by advancing (A[1], A[2], A[3], ..., A[n] to the next permutation in the lexicographic ordering. If (A[1], A[2], A[3], ..., A[N] is already at the end of the sequence, the function will resets to the initial permutation (1, 2, 3, ..., n) in the lexicographic order. The pseudo-code below gives an Outline for the body of nextPermutation (). scan the array from right-to-left if the current element is less than its right-hand neighbor call the current element the pivot stop scanning if the left end was reached without finding a pivot reverse the array (permutation was lexicographically last, so start over) return scan the array from right-to-left again if the current element is larger than the pivot call the current element the successor stop scanning swap the pivot and the successor reverse the portion of the array to the right of where the pivot was found returnExplanation / Answer
class NextPermutation
{
static void nextPermutation(int[] A)
{
int n = A.length;
n--;
int pivot = -1;
int i;
for(i = n-1; i >= 1; i--)
if(A[i] < A[i+1])
{
pivot = i;
break;
}
if(i == 0 && pivot == -1)
{
for(i = 1; i <= n/2; i++)
{
int temp = A[i];
A[n-i+1] = A[i];
A[i] = temp;
}
return;
}
int successor = -1;
for(i = n-1; i >= 1; i--)
if(A[i] > A[pivot])
{
successor = i;
break;
}
int temp = A[pivot];
A[pivot] = A[successor];
A[successor] = temp;
for(i = pivot+1; i <= (n-pivot)/2; i++)
{
temp = A[i];
A[n-i+1] = A[i];
A[i] = temp;
}
return;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.