Algorithm to generate an array with n length and k number of inversions in O(n log n) time?

Question

I'm writing an algorithm that will return an array with determined length and number of inversions (number pairs, where the left side number is larger than the right side number). I.e. array [3, 1, 4, 2] contains three inversions (3, 1), (3, 2) and (4, 2). So in practice, when given the length of n=3 and number of inversions k=3, the algorithm should generate an array [3, 1, 4, 2] (or another array that fulfills these requirements).

Since the number of inversions is also the number of swaps that has to be made for the array to be sorted in ascending order, I approached this problem by creating an array from 1 to n - 1 and using an insertion sort algorithm in reverse to make k swaps.

This approach works just fine for smaller inputs, but the algorithm should be able to efficiently generate arrays up to n=10^6 and k=n(n-1)/2 and anything in between, so the algorithm should be working in O(n log n) time instead of O(n^2). Below is the code:

import java.util.*;

public class Inversions {

    public int[] generate(int n, long k) {        

        // Don't mind these special cases

        if (n == 1) {

            int[] arr = {1};

            return arr;
        }

        if (k == 0) {

            int[] arr = new int[n];

            for (int i = 0; i < n; i++) {

                arr[i] = 1;                    
            }

            return arr;
        }

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {

            arr[i] = i + 1;
        } 

        int inversions = 0;
        int i = 0;    

        while (inversions < k && i < n) {                                    

            int j = i - 1;                        

            while (j >= 0 && arr[j] < arr[j + 1] && inversions < k) {

                int helper = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = helper;
                inversions++;
                j--;
            }     

            i++;
        }

        return arr;
    }
}

And the main class for testing with different input arrays:

public class Main {

    public static void main(String[] args) {

        Inversions in = new Inversions();
        int[] arr1 = in.generate(4,3);
        int[] arr2 = in.generate(4,0);
        int[] arr3 = in.generate(4,6);        

        System.out.println(Arrays.toString(arr1)); // [3,1,4,2]
        System.out.println(Arrays.toString(arr2)); // [1,1,1,1]
        System.out.println(Arrays.toString(arr3)); // [4,3,2,1]
    }
}

The algorithm does not return exactly the same arrays as the sample results, but passes all the tests, except the ones where the input size is very large. I have also tried different variations with merge sort, since it's working in O(n log n time) but with no avail.

It would be great if you guys have some ideas. If you are not familiar with Java, doesn't matter, pseudocode or any other kinds of suggestions are more than welcome!

Answer 1

If you reverse the initial m elements in the array, you create m(m-1)/2 inversions.

If you reverse the initial m+1 elements, you create m(m+1)/2 inversions.

The difference between these is only m.

So:

1. Generate a sorted array
2. Find the largest m such that m(m-1)/2 <= k
3. Reverse the first m elements in the array to create m(m-1)/2 inversions
4. Shift the next element forward k - m(m-1)/2 positions to create the remaining required inversions.

This takes O(n) time, which is better than you require.

Answer 2

Another O(n) algorithm: Start with a sorted array. When you swap the first and last elements, you get x = 2 * (n-2) + 1 inversions. Consider these two elements fixed and work on the remaining array only. If x is too large, consider a smaller array. Repeat this as long as needed.

Untested code:

for (int first=0, last = n-1; remainingInversions>0; ) {
    int x = 2 * (last-first-1) + 1;
    if (x <= remainingInversion) {
        first++;
        last--;
        remainingInversion -= x;
    } else {
        last--; // consider a smaller array
    }
}