Numpy Slicing problem: Possible way to reduce array size while retaining the boundaries condition, equal spacing elements and symmetry around 0

Question

I want to finding a general formula or algorithm to determine all possible values of `step` that satisfy the three conditions (boundary, equal spacing, and symmetry) when slicing an array with the same properties.

Let says I have an initial_array = np.linspace(-10, 10, 11)

[-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10]

I want to slice the array such that the reduced_array retains 3 condition:

1. Boundary condition. The minimum and maximum elements should remain unchanged.
2. Equal spacing property. Spacing between each elements should be constant.
3. Symmetry property. The whole array should have an symmetry around zero, whether or not the zero is included in the array.

One way to slice the initial_array is to set reduced_array=initial_array[::2], which get us

[-10, -6, -2, 2, 6, 10]

For initial_array = np.linspace(-10, 10, 21),

[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

I can slice it by setting reduced_array=initial_array[::2],

[-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10]

or reduced_array=initial_array[::4]

[-10, -6, -2, 2, 6, 10]

Right now, I am trying to find out, for an arbitrary size of array

#initial condition
max = 200 
min = -max 
size= 314 
initial_array = np.linspace(min,max,size)  

step= ? #unknown, to be solved
reduced_array = initial_array[::step] 

Some pattern I observed is that for size of 11,21 and 31, value of step is the factor of 10,20 and 30 etc.

Clearly, step<=floor(size/2). Ultimately, I want to locate the reduced_array which does not include 0. One application for me is to create a high resolution linspace for calculation. Then, when doing visualization, I slice it down to a much smaller size for plotting. One example of wanting to exclude 0 from the reduced array is when 0 is a singularity point that cannot be visualized.

How many and how can I slice the array while keeping all 3 proposed conditions? Is there a way to formulate the problem mathematically?

Answer 1

Following up on the factorization idea, you can actually perform this in O(n) space and time. Finding primes is hard, but checking divisibility is easy.

For a given array a and step n, your conditions boil down to that (len(a) - 1) % n == 0. Furthermore, n is in the range [1, len(a) / 2). Finding all suitable values is very simple in numpy:

n = np.arange(1, (len(a) + 1) // 2)
n = n[(len(a) - 1) % n == 0]

This will create an array of all possible n meeting the condition. You can index with it using something like

a[::n[k]]

for some selection k. You can also create a slice object that represents the same index:

s = slice(None, None, k)
a[s]

In your example:

a = np.array([-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10])

This makes n

n = [1, 2, 5]

So you have the subsets

k = 0: [-10, -8, -6, -4, -2, 0, 2, 4, 6, 8 10]
k = 1: [-10, -6, -2, 2, 6, 10]
k = 2: [-10, 0, 10]

You can observe that zero is a member of the slice whenever ((len(a) - 1) // 2) % n == 0. This only makes sense for odd-sized arrays to begin with of course, since even-sized arrays can not be symmetrical and contain zero at the same time. Adding this new condition to the calculation of n is left as an exercise for the reader.

Answer 2

The conditions are simply any step size that is a factor of array_length-1 and is less than or equal to (array_length - 1)/2. If you're also fine with the array only being the first and last indices then the step size can also be array_length-1.

import math
import numpy as np

def get_factors_less_than_half(number):
    """
    Returns a list of factors of `number` less than 
    or equal to half that number. This can easily be
    vectorized using numpy.
    """
    factors = []
    for i in range(1, number//2+1):
        if number % i == 0:
            factors.append(i)
    return factors

# Testing code
for i in range(11, 500):
    initial_array = np.linspace(-100, 100, i)
    steps = get_factors_less_than_half(i-1) + [i-1]
    
    for step in steps:
        stepped_array = initial_array[::step]
        assert stepped_array[0] == -stepped_array[-1], "The first and last don't match"
        if len(stepped_array) > 2:
            assert math.isclose((stepped_array[1] - stepped_array[0]), 
                                (stepped_array[2] - stepped_array[1])), \
                "The step size isn't constant"

Answer 3

This is an alternative to Jared's excellent response.

arrA = [ -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

arrB = [ -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

  # in this function we simply add to the output, the values whose 
  # position coincides with the jump
def odd( arr, num ):
    out = []
    for i in range( len( arr )):
        if i % num == 0:
            out.append( arr[ i ])
    return out


  # in this function we add to the output, the values whose position 
  # coincides with the jump, but when we get to the middle of the array, 
  # we introduce a small jump in the compared value 
def even( arr, num ):
    limit = int( len( arr ) / 2 )
    out = []
    x = 0
    for i in range( len( arr )):
        if i == limit:
            x = 1
        if ( i + x ) % num == 0:
            out.append( arr[ i ])
    return out


  # this function determines which function we will use based on the 
  # length of the array
def slimming( arr, num ):
    try:
        arr.index( 0 )
        return odd( arr, num )
    except:
        return even( arr, num )
        
print( slimming( arrA, 2 ))
    -> [-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10]

print( slimming( arrB, 2 ))
    -> [-10, -8, -6, -4, -2, 2, 4, 6, 8, 10]

PS: Obviously, the same result can be obtained with only one function, I have put it in this way, to make it clearer