Minimizing Autocorrelation of a List

As part of a graph rendering algorithm, I needed to take a list of y-values and disperse the points within a xy-range. (Within the list, the x coordinate has no meaning. I'm not re-ordering a time series.) To model the dispersion, I decided to use the autocorrelation metric. Autocorrelation measures the correlation of a list to itself. Put another way, autocorrelation measures how much the prior value can be used to predict the next value. (For this discussion, I'm using 1 as the lag parameter. Additionally, minimizing the autocorrelation is the same as minimizing the covariance.)

For example, the figure below shows a sinusoid (sampled at a regular interval). The autocorrelation of the figure is 0.994705 --- almost the maximum value of 1.

In contrast, the figure below has been modified by the autocorrelation minimization algorithm. The two figures have the same y-values, but the x-values have been changed resulting in a new correlation of -0.999955.

The Algorithm

The formula for calculating autocorrelation includes a number of terms, but the only terms that are impacted by changing the order of the list can be reduced to the sum:

$$ \Sigma(x_i - \mu)(x_{i+1} - \mu) $$

where \(\mu\) is the arithmetic mean of the list.

The approach is to maximize occurrences of large negative values.

1. Create a list terms with the values of the list minus the mean of the list.
2. Sort the list terms.
3. Initialize the merged list with the head and tail of terms.
4. While elements remain in terms,
1. Take an element from terms (either the head or tail) such that the element minus the mean multiplied by the head or tail of merged has minimal value.
5. Add the mean to each element of merged. Return that list.

I've uploaded a Python implementation of the algorithm to Gist.

Updated: Algorithm simplified