Inversions.java

/* *****************************************************************************
 *  Name:              Ada Lovelace
 *  Coursera User ID:  123456
 *  Last modified:     October 16, 1842
 **************************************************************************** */

public class Inversions {
    public static long count(int[] a) {
        long count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) count++;
            }
        }
        return count;
    }

    // Return a permutation of length n with exactly k inversions.
    public static int[] generate(int n, long k) {
        int c = 0;
        int[] generated = new int[n];
        for (int i = 0; i < n; i++) {
            int positionShift2Left;
            if (k > (n - 1 - i))
                positionShift2Left = (int) ((n - 1 - i) % k);
            else positionShift2Left = (int) k;
            if (positionShift2Left != 0)
                generated[n - 1 - positionShift2Left] = n - 1 - i;
            k = k - positionShift2Left;
            if (generated[i] == 0) generated[i] = c++;
        }
        return generated;
    }

    // Takes an integer n and a long k as command-line arguments,
    // and prints a permutation of length n with exactly k inversions.
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        long k = Long.parseLong(args[1]);
        int[] a = generate(n, k);
        for (int i = 0; i < n - 1; i++)
            System.out.print(a[i] + " ");
        System.out.println(a[n - 1]);
    }
}