Description
• Your task is to design and implement an algorithm to convert
permutation inversion vector W into the corresponding
permutation A
• For a permutation A of numbers 1..N:
– Inversion vector W of length N has j
th element W[j] defined as:
– W[j] = number of elements in A[1.. j-1] that are larger than A[j]
– 0<=W[j]<=j-1
• To obtain permutation A from permutation inversion vector W
of length N
– Read W from end, fill A from the end with unused elements from
1..N
• Ex: with N=5, W=[0,1,1,1,2] => A=[5,1,2,4,3]
• See also Lecture 04, slides 28-32.
Input-output formats
• Take integers from standard input (System.in):
– Line 1: single integer specifying N: number of
elements in permutation (1<=N<=1000) (N =
length of W = length of A)
– Lines 2 to N+1: line j contains an integer that
goes into W[j-1]
• print permutation A corresponding to the
input inversion vector W to standard output
(System.out), with each integer on a separate line
• As always, do not print any text or blank lines to standard output except the integers
-Example:
-Input:
5
0
1
1
1
2
-Correct Output:
5
1
2
4
3
Submission
• Date due: Thursday, Sept 22th, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
1_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case
letters!)
– The file should have your name in a comment in the first line
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT use packages
• Do NOT place the file into a folder – just zip the file
