An important metric in the theory of sorting is the number of inversions in a sequence.
An inversion is any pair of elements that are out of order, meaning that the earlier element in the sequence has a larger value than the later element in the sequence. For example, the sequence
3 1 4 2 5
has three inversions: 3-1, 3-2, and 4-2.
Given integers n and inv, you are to return a permutation of the sequence 1,...,n that has
exactly inv inversions. If it is not possible to create a permutation that has inv inversions, return the empty sequence. If there is more than one permutation that has exactly inv inversions, return the lexicographically earliest.
A permutation P is lexicographically earlier than a permutation Q if, at the first index at which the permutations differ, the element in P is smaller than the element in Q.
|