Problem I: Sort of Continued Lines
Your task is to write a C program named I.c according to the specifications below.
You should be familiar with the program sort that can sort lines of a textual file in various ways using the keys. A simple sort will just sort lines alphabetically, or to be more precise in the ASCII order using the characters in the line and using the lexicographic order.
In some situations, we may want to keep several lines together and we do not want to break them in sorting. For example we can indicate that a line continues into the next line by using the backslash character at the very end of the line. Your task is to write a sorting program that sorts lines in such way that the continued lines are not broken. The continued lines should be sorted and compared to each other as long strings using the function strcmp.
Since there is not specified limit on the number of lines or the length of one line, it is recommended that you use malloc and realloc functions to allocate for each continued line exactly as much memory as required. You can read all continued lines into a linked list, then sort the list, and print them from the list.
Input
The standard input includes an arbitrary text. There are no specified limitations to the number of of lines or the length of lines.
Output
Your program must keep continued lines in a group, where any line continues to the next line if there is the backslash character at the very end of the line, and the program must printed the continued lines in a sorted order. Of course, the continued line can be mixed with single lines that are not part of any group.
Sample input and output are given below:
Note: is a space, and n is a newline character.
Problem J: Ordered Permutations
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:
while the lexicographically ordered permutations would be:
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).
You should write a program that generates permutations in the lexicographically ordered way. The program must have two modes of operation, in one the program must produce all permutations, and in other it must produce only the permutation that comes at certain position in the permutations list.
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 k == n-1 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: Permute(A, k+1, n)
7: swap A[k] with A[i] /* swap back */
In order to get lexicographic order, in the step 5, you should not just swap A[k] and A[i], but you need to rotate all elements from A[k] to A[i], by moving A[k + 1] into A[k], A[k + 2] into A[k + 1], and so on, until you move A[i] into A[i 1], and finally move the old value of A[k] into A[i]. Similarily in the step 7 you need to reverse this rotation.
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 input, your program should first produce the line that 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 m = 0 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 all 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:
Note: is a space, andn is a newline character.
