Description
-
Write an array–returning function FINDORDER(A,N) which returns an integer array ordering the elements of the integer array A[1 : N], i.e., which returns such an array R[1 : N], that:
A[R[I]] ≤ A[R[J]] for 1 ≤ I < J ≤ N.
For example, if A = [1, 3, 6, 3, 2, 6, 5], the returned array is [1, 5, 2, 4, 7, 3, 6], i.e., the sequence A[R[1]], A[R[2]], … is ordered.
Write also a Fortran program which reads the data, invokes FINDORDER and prints the results.
-
Permutations of N elements can be systematically generated using an integer N–element array, initialized to [1, 2, …, N], and systematically rearranging elements of this array. For example, if N = 5, the consecutive permutations are:
[1,2,3,4,5]
[1,2,3,5,4]
[1,2,4,3,5]
[1,2,4,5,3]
[1,2,5,3,4]
[1,2,5,4,3]
[1,3,2,4,5]
………..
[5,4,3,2,1]
Write a logical Fortran function NEXTPERM(A,N) which generates the next permutation of elements of an integer array A[1 : N] and returns TRUE if the next permutation exists; otherwise FALSE is returned.
Write also a Fortran program which reads the data, invokes NEXTPERM several times and prints the results.
Hint: The next permutation can be generated by searching from the right end of A for the first pair of increasing consecutive elements. Let the first element of this pair be denoted X. X is swapped with the smallest element greater than X among the elements following X, and then the part following (the original) X is ordered. For example. if A = [1, 2, 5, 4, 3], the first pair of increasing elements from the right end is (2, 5), so X = 2. It is swapped with 3 and then the last 3 elements of A are ordered, so the generated permutation is A = [1, 3, 2, 4, 5]. If A = [3, 5, 4, 2, 1], the next permutation is A = [4, 1, 2, 3, 5]. There are N! permutations of N elements.
