interpolate python array to minimize maximum difference between elements
Question: What is a concise and readable way of interpolating a 1D array such that the
maximum difference between elements is minimized?

For instance, if I had the array [4 9 13 25] and I was allowed to add 1 more
number in order to minimize the maximum difference between elements I would
insert a 19 between 13 and 25 (max difference is now 6 rather than 12).

Of course a good ole' for loop will get it done, but for posterity is there a
less verbose approach than below?

    
    
    # current array
    nums = np.array([4.0, 9.0, 13.0, 25.0])
    # size of new array
    N=10
    
    # recursively find max gap (difference) and fill it with a mid point    
    for k in range(N-len(nums)):
        inds = range(len(nums))
        # get the maximum difference between two elements
        max_gap = np.argmax(np.diff(nums))
        # put a new number that's equidistant from the two element values
        new_num = np.interp(np.mean([inds[max_gap],inds[max_gap+1]]), inds, nums)
        nums = np.insert(nums, max_gap+1, new_num)
        print nums
    

This example interpolates the 1D array, filling regions where the greatest
difference was:

    
    
    [  4.   9.  13.  19.  25.]
    [  4.   9.  13.  16.  19.  25.]
    [  4.   9.  13.  16.  19.  22.  25.]
    [  4.    6.5   9.   13.   16.   19.   22.   25. ]
    [  4.    6.5   9.   11.   13.   16.   19.   22.   25. ]
    [  4.    6.5   9.   11.   13.   14.5  16.   19.   22.   25. ]
    

**edit 1:** As comments suggest, there is a trade-off between readability,
efficiency, and accuracy. Of these three attributes, for me the most important
is readability. I still give +1 for any and all improvements to my above
algorithm though since it is a general problem and any answer that improves
either of those three attributes is beneficial to someone if not me later on.


Answer: And, if you want efficiency for long arrays, even if the code is not as short,
I suggest:

    
    
    nums = np.array([4., 9., 13., 25])
    diffs = np.diff(nums)
    N = 10
    
    # Number of interpolation points proportional to length of gaps
    new_points = diffs/sum(diffs) * (N-len(nums))
    while sum(np.floor(new_points)) != N -len(nums): # from continuum to discrete 
        pos = np.argmax(new_points - np.floor(new_points))
        new_points[pos] = np.floor(new_points[pos] + 1)
    new_points = np.floor(new_points)
    
    # Now we interpolate by inserting linspace values starting from the end to 
    # avoid the loop limits being spoiled when introducing values. 
    for ii in range(len(new_points))[::-1]:
        #linspace includes borders
        introduce_these = np.linspace(nums[ii], nums[ii+1], new_points[ii] + 2)[1:-1]
        nums = np.insert(nums, ii+1, introduce_these)
    

That produces:

    
    
    In [205]: print nums
    [4.   5.66666667   7.33333333   9.   11.   13.   16.   19.   22.   25. ]
    

