## Description

Inversion Vector

• 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

9/9/16 3

-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