Is there an algorithm to redistribute an array equally?-CodePudding

I have a one-dimensional array of non-negative integers. When plotted as a histogram, the range is mostly smaller numbers:

Is there an algorithm to redistribute the values more equally while maintaining the original order? By order I mean the minimum and maximum values would retain their original places in the array and everything else in between would scale up or down. When plotted afterwards the histogram would be more or less flat.

Searching the web I came across a "probability integral transform" in statistics, but that required sorting the data.

EDIT - Apologies for omitting why I don't want to sort it. The array is a plot and each integer represents a pixel. If I sort it that would destroy the plot. I'm dividing each integer by the maximum value and using that as an index into a palette. Because there's so much bias towards smaller values, only a small amount of the palette is visible in the final image. I thought if I was able to redistribute the values somehow, it'd use the full range of the palette.

CodePudding user response：

You could apply this algorithm:

Let c be a freely chosen coefficient between 0 and 1: the closer to 1 the more close the resulting values will be to each other. If exactly 1, then all values will be equal. If 0, the result will be the original data set. A candidate value for c could for instance be 0.9
Let avg be the average of the input values
Apply the following transformation to each value in the input set:

new value := value * (1 − c) avg * c

Here is an interactive implementation in a JavaScript snippet:

let a = [150, 100, 40, 33, 9, 3, 5, 13, 8, 1, 3, 2, 1, 1, 0, 0];
let avg = a.reduce((acc, val) => acc   val) / a.length;

function refresh(c) {
    // Apply transformation from a to b using c:
    display(a.map(val => val * (1 - c)   avg * c));
}

// I/O management

var display = (function (b) {
    this.clearRect(0, 0, this.canvas.width, this.canvas.height); // Clear display
    for (let i = 0; i < b.length; i  ) {
        this.beginPath();
        this.rect(20   i * 20, 150 - b[i], 19, b[i]);
        this.fill();
    }
}).bind(document.querySelector("canvas").getContext("2d"));

document.querySelector("input").oninput = e => refresh( e.target.value);
refresh(0);

Coefficient: <input type="number" min="0" max="1" step="0.01" value="0"><br>
<canvas height="150" width="400"></canvas>

Use the Coefficient input box to experiment with different values for it on a sample data set.

In Python the transformation, for a given list a and coefficient c, could look like this:

avg = sum(a) / len(a)
b = [value * (1 - c)   avg * c for value in a]