讲解C program、辅导Permutation、辅导C/C++程序、C/C++讲解
解析Haskell程序|辅导Web开发
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:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
...
while the lexicographically ordered permutations would be:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
...
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:Sample Input Sample Output
0 3 Permutations of 3:
3 4 1 2 3
4 4 1 3 2
5 4 2 1 3
30 4 2 3 1
0 0 3 1 2
3 2 1
Permutation of 4 number 3:
1 3 2 4
Permutation of 4 number 4:
1 3 4 2
Permutation of 4 number 5:
1 4 2 3
Permutation of 4 number 30:
End of output
Sample Output, with
visualized whitespace
Permutations of 3:\n
1 2 3\n
1 3 2\n
2 1 3\n
2 3 1\n
3 1 2\n
3 2 1\n
Permutation of 4 number 3:\n
1 3 2 4\n
Permutation of 4 number 4:\n
1 3 4 2\n
Permutation of 4 number 5:\n
1 4 2 3\n
Permutation of 4 number 30:\n
End of output\n
Note: is a space, and \n is a newline character.