a) [10 marks] Functionality: To satisfy this requirement, your program must satisfy the program requirements as specied and pass the practicum testing. b) [5 marks] Implementation: To receive these marks, the program must be implemented in the following way, and it will be marked by a marker. You are required to write a head comment that includes your name, date of the program, the course and assignment number, and a short description of the program. The program should follow the organization presented in the class. The program should use an appropriate indentation. Each block should have a consistent indentation, which can be any number of spaces you choose, between 2 and 8. You can choose a reasonable brace placement style (for example, see https://en.wikipedia.org/wiki/Indentation_style). K&R style would be recommended, but any other known style is acceptable as well. Your program lines should not be longer than 80 characters. The program should use the above method, although alternative methods are also acceptable if they are correct and equally or more ecient. If the input requires that you print only one permutation, the program should not continue generating unnecessary permutations internally, but move to the next case.

Your task is to write a C program named J.c according to the following specifications. We covered in class generation of all permutations of numbers 1, 2,...n. However, as we noticed, the generated permutations were not lexicographically ordered. For example, for n- 4 the generated permutations were 1 2 34 1 243 1 3 24 1 3 4 2 1 4 32 while the lexicographically ordered permutations would be: 1 2 34 1 243 1 3 24 1 3 4 2 1 4 23 If you are not familiar with lexicographic order, we can define it in the following way: We compare two sequences of numbers (or letters, or other comparable elements), from the start and keep doing it while the sequence elements are equal. When we come across the first elements that are different, we decide that sequences compare in the same way as those two elements. In the above example, when we compare sequences (1,4,3,2) and (1,4,2,3), we see that the sequences differ first time at the third position, and the sequence with 2 at the third position should come before the sequence with 3 at third position; i.e., the order should be (1,4,2,3) and then (1,4,3,2) Input Each line of input contains two integers m and n. The input ends with integers 0 and 0. Other than the final two numbers, n is always the positive integer. If the first number m is 0, you program must print all permutations of numbers 1, 2,... , n in the lexicographic order. If the number m is positive, then your program must print only the m'th permutation of numbers 1, 2,..., n in the lexicographic order. If the number m is so large that you run out of permutation, your program should not print anything. Output For each par of numbers m and n in the im should ins produce tenthat looks as follows: If n is 0, the line should be: End of output otherwise, if m is 0, the line should be: Permutations of n: otherwise, the line should be: Permutation of n number m: After that, if m0 and n > 0 the program must produce all permutations as specified, one permutation per line; or if m > 0 only the specified permutation, or no permutations at al if m is larger than the number of permutations, and if both m and n are zero, then the program should end Sample input and output are given below: Method You should base your method on the algorithm covered in class. If you remember the algorithm (one version) from Lecture 19 was: 1 IF k1 THEN print A 2: ELSE 3: Permute (A, k+1, n) 4: FOR i -k+1 TO n-1 DO 5: swap A[k] with A[i] 6: 7 Swap A[k] with A[i / swap back/ Permute (A, k+1, n) In order to get lexicographic order, in the step 5, you should not just swap Alk] and Ali], but you need to rotate all elements from Alk] to A[i], by moving A(k + 1] into , Alk + 2] into Alk + 1), and so on, until you move Ali] into Ali 1], and finally move the old value of Alk] into Ali Similarily in the step 7 you need to reverse this rotation. Sample I 0 3 Sample Output Permutations of 3: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 30 4 Permutation of number 3: Permutation of 4 number 4: Permutation of 4 number 5: Permutation of 4 number 30: 1 3 2 4 1 3 4 2 1 4 2 3 End of output Output, with Sample visualized white Permutations of-3: 123 13 20 2 1 3 2-3 1 3 1 2 3-2 1 Permutation of-4 number 3:T 13-2 4 Permutation of-4 number 4:T 13-4-20 Permutation of 4number 5: 1-4 230 Permutation of 4-number-30:C End of.outputr Note: is a space, and is a newline character Your task is to write a C program named J.c according to the following specifications. We covered in class generation of all permutations of numbers 1, 2,...n. However, as we noticed, the generated permutations were not lexicographically ordered. For example, for n- 4 the generated permutations were 1 2 34 1 243 1 3 24 1 3 4 2 1 4 32 while the lexicographically ordered permutations would be: 1 2 34 1 243 1 3 24 1 3 4 2 1 4 23 If you are not familiar with lexicographic order, we can define it in the following way: We compare two sequences of numbers (or letters, or other comparable elements), from the start and keep doing it while the sequence elements are equal. When we come across the first elements that are different, we decide that sequences compare in the same way as those two elements. In the above example, when we compare sequences (1,4,3,2) and (1,4,2,3), we see that the sequences differ first time at the third position, and the sequence with 2 at the third position should come before the sequence with 3 at third position; i.e., the order should be (1,4,2,3) and then (1,4,3,2) Input Each line of input contains two integers m and n. The input ends with integers 0 and 0. Other than the final two numbers, n is always the positive integer. If the first number m is 0, you program must print all permutations of numbers 1, 2,... , n in the lexicographic order. If the number m is positive, then your program must print only the m'th permutation of numbers 1, 2,..., n in the lexicographic order. If the number m is so large that you run out of permutation, your program should not print anything. Output For each par of numbers m and n in the im should ins produce tenthat looks as follows: If n is 0, the line should be: End of output otherwise, if m is 0, the line should be: Permutations of n: otherwise, the line should be: Permutation of n number m: After that, if m0 and n > 0 the program must produce all permutations as specified, one permutation per line; or if m > 0 only the specified permutation, or no permutations at al if m is larger than the number of permutations, and if both m and n are zero, then the program should end Sample input and output are given below: Method You should base your method on the algorithm covered in class. If you remember the algorithm (one version) from Lecture 19 was: 1 IF k1 THEN print A 2: ELSE 3: Permute (A, k+1, n) 4: FOR i -k+1 TO n-1 DO 5: swap A[k] with A[i] 6: 7 Swap A[k] with A[i / swap back/ Permute (A, k+1, n) In order to get lexicographic order, in the step 5, you should not just swap Alk] and Ali], but you need to rotate all elements from Alk] to A[i], by moving A(k + 1] into , Alk + 2] into Alk + 1), and so on, until you move Ali] into Ali 1], and finally move the old value of Alk] into Ali Similarily in the step 7 you need to reverse this rotation. Sample I 0 3 Sample Output Permutations of 3: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 30 4 Permutation of number 3: Permutation of 4 number 4: Permutation of 4 number 5: Permutation of 4 number 30: 1 3 2 4 1 3 4 2 1 4 2 3 End of output Output, with Sample visualized white Permutations of-3: 123 13 20 2 1 3 2-3 1 3 1 2 3-2 1 Permutation of-4 number 3:T 13-2 4 Permutation of-4 number 4:T 13-4-20 Permutation of 4number 5: 1-4 230 Permutation of 4-number-30:C End of.outputr Note: is a space, and is a newline character