代做C program、代写Permutation、代写C/C++程序、C/C++代做

日期：2018-11-28 10:36

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.