3
$\begingroup$

I am trying to find a lead on how to solve or find a heuristic the following kind of problem:

Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a given form, generate indices for the 1 entries in the array/matrix.

The looping function/pattern is as followings:

index = (z_offset + z_i) * z_stride + 
        (y_offset + y_i) * y_stride + 
        (x_offset + x_i) * x_stride

The values are generated with loops.

indices = []

for z_i in range(0, z_dim)
    for y_i in range(0, y_dim)
        for x_i in range(0, x_dim)
            index = (z_offset + z_i) * z_stride + 
                    (y_offset + y_i) * y_stride + 
                    (x_offset + x_i) * x_stride
            indices.append(index)

For example the indices for the 1s in this array can be generated with these parameters:

x_dim = 3, y_dim = 1, z_dim = 2
x_stride = 1, y_stride = 3, z_stride = 6
x_offset = y_offset = z_offset = 0

[1 1 1
 0 0 0 
 1 1 1]

These are the array entries indices and the indices made by the loop:

[0 1 2
 3 4 5
 6 7 8]

[0 1 2 6 7 8]

Notice if thought of as a matrix the size of the matrix doesn't matter because the indices would still be the same. e.g.

[1 1 1 0
 0 0 1 1 
 1 0 0 0]

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

Another example, now with offsets:

x_dim = 2, y_dim = 2, z_dim = 3
x_stride = 1, y_stride = 2, z_stride = 7
x_offset = 1, y_offset = z_offset = 0

[0 1 1 1 1
 0 0 1 1 1 
 1 0 0 0 0]

So now the problem is the reverse and in two parts. If you are given a set of indices (e.g. [0 1 2 6 7 8]) find the parameters for this function (x_dim, y_dim, z_dim, x_stride, y_stride, z_stride, x_offset, y_offset, z_offset)

Find an exact or heuristic way to do that would be great but the second part of the problem is more difficult. If the indices do not map exactly to a single set of parameters then find a set of parameters for N functions (e.g. (x_dim_0, y_dim_0, ... z_offset_0), (x_dim_1, y_dim_1, ... z_offset_1), ... (x_dim_N, y_dim_N, ... z_offset_N)

Ideally there would be a solution for finding the minimum number of parameter sets but a heuristic that just finds a solution would be good too. Also, Ideally the parameter sets would be orthogonal (i.e. none of the indicies one set produces are the same as the indices another set produces)

EDIT: To clarify the inputs to the algorithm is the array of incides (e.g. [3 4 5 9 10 11]). I'd like to have an approach for an array of indices of any size but I imagine practically the max size would be around 64*64*5 ~= 20000 and typically 32*32*3 3072 but maybe as small as 8*8*3 = 192

If anybody has any insight how to approach or solve this problem any help would be appreciated!

$\endgroup$
  • 1
    $\begingroup$ I'm having a hard time understanding what you're trying to achieve. For instance, I'm confused by your second code sample, where in each iteration of the inner loop, you overwrite index. Is that a typo? What are the inputs to the algorithm you're trying to write, and what are the outputs? What relationship do the outputs have to have to the input? What approaches have you considered? Have you tried search over all possible parameter values? How large is the input array, in practice? $\endgroup$ – D.W. Aug 20 '16 at 17:06
  • $\begingroup$ Hi. I answered your questions about size in the edit and updated the code. The "index" is added to an array each time a new index is generated. The input to the algorithm is the array of indices and the output of N sets of the 9 parameters (x_dim, y_dim ... z_offset). Because of those sizes I'm not sure if the input space is searchable because you have 9*N parameters where N may be anything from 1 to N depending on how complex the pattern is. $\endgroup$ – ballaw Aug 20 '16 at 18:41
  • 1
    $\begingroup$ What is the actual goal here? Is it compression of sparse binary matrices? If so, one option is to use straight line programs (ieeexplore.ieee.org/xpl/…). Alternatively, you could use Genetic Programming to try and learn the expression inside your triply-nested loop. $\endgroup$ – NietzscheanAI Aug 21 '16 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.