MM26 Java Solution (5800000 cycles)

Permute.java

public class Permute {
	long limit = 5_800_000;
	public int[] findOrder(double[] w) {
		
		int n = (int)Math.sqrt((double)w.length);
		int[] ret = new int[n];
		for (int i = 0; i < n; i++) {
			ret[i] = i;
		}
		
		double sc = 0.0;
		for (int i = 0; i < n - 1; i++) {
			int rn = ret[i] * n;
			for (int j = i + 1; j < n; j++) {
				sc += w[rn + ret[j]];
			}
		}
		
		long lp = 0;
		int a = 0, b = 1;
		
		while (lp < limit) {
			
			lp++;
			
			int ra = ret[a];
			int rb = ret[b];
			int ran = ra * n;
			int rbn = rb * n;
			
			double dsc = w[rbn + ra] - w[ran + rb];
			for (int i = a + 1; i < b; i++) {
				int r = ret[i];
				int rn = r * n;
				dsc += w[rbn + r] + w[rn + ra] - w[ran + r] - w[rn + rb];
			}
			
			if (dsc > 0.0) {
				ret[a] = rb;
				ret[b] = ra;
				sc += dsc;
			}
			
			b++;
			if (b >= n) {
				a++;
				if (a >= n - 1) {
					a = 0;
				}
				b = a + 1;
			}
		}
		
		double dv = (double)n * Math.sqrt((double)n * Math.log((double)n) - (double)n) / 100.0;
		sc /= dv;
		
		System.err.println("score=" + sc);
		System.err.println("loop=" + lp);
		
		return ret;
	}
}