Algoritmo para subdividir una matriz en sub-arrays uniformes "semi-iguales"

Question

Dado una matriz con N elementos, estoy buscando M-sub-matrices M (M < N) con longitudes iguales o con longitudes que difieren en su mayoría 1. Por ejemplo, si N = 12 y M = 4, todas las sub-matrices tendrían longitudes iguales de N/M = 3. Si N = 100 y M = 12, espero sub-arrays con longitudes 8 y 9, y ambos tamaños deben distribuirse uniformemente dentro del conjunto original. Esta simple tarea resultó ser un poco sutil para implementar. Vine con una adaptación de la Bresenham's line algorithm, que se parece a esto cuando codificado en C++:

/// The function suggests how an array with num_data-items can be 
/// subdivided into successively arranged groups (intervals) with 
/// equal or "similar" length. The number of intervals is specified 
/// by the parameter num_intervals. The result is stored into an array 
/// with (num_data + 1) items, each of which indicates the start-index of 
/// an interval, the last additional index being a sentinel item which 
/// contains the value num_data. 
/// 
/// Example: 
/// 
/// Input: num_data ........... 14, 
///   num_intervals ...... 4 
/// 
/// Result: result_start_idx ... [ 0, 3, 7, 10, 14 ] 
/// 

void create_uniform_intervals(const size_t   num_data, 
           const size_t   num_intervals, 
           std::vector<size_t>& result_start_idx) 
{ 
    const size_t avg_interval_len = num_data/num_intervals; 
    const size_t last_interval_len = num_data % num_intervals; 

    // establish the new size of the result vector 
    result_start_idx.resize(num_intervals + 1L); 
    // write the pivot value at the end: 
    result_start_idx[ num_intervals ] = num_data; 

    size_t offset  = 0L; // current offset 

    // use Bresenham's line algorithm to distribute 
    // last_interval_len over num_intervals: 
    intptr_t error = num_intervals/2; 

    for(size_t i = 0L; i < num_intervals; i++) 
    { 
     result_start_idx[ i ] = offset; 
     offset += avg_interval_len; 
     error -= last_interval_len; 
     if(error < 0) 
     { 
      offset++; 
      error += num_intervals; 
     } // if 
    } // for 
} 

Este código calcula las longitudes de intervalo para N = 100, M = 12: 8 9 8 8 9 8 8 9 8 8 9 8

La verdadera pregunta es que no sé exactamente cómo llamar a mi problema, así que tuve dificultades para buscarlo.

• ¿Existen otros algoritmos para llevar a cabo dicha tarea?
• ¿Cómo se llaman? Tal vez los nombres vendrían si conociera otras áreas de aplicación.

Necesitaba el algoritmo como parte de un algoritmo más grande para la agrupación de datos. Creo que también podría ser útil para implementar un tipo paralelo (?).

Answer 1

Si su lenguaje tiene división entera que trunca, una manera fácil de calcular el tamaño de la sección i es a través de (N*i+N)/M - (N*i)/M. Por ejemplo, el programa de pitón

N=100;M=12 
    for i in range(M): print (N*i+N)/M - (N*i)/M 

emite los números 8 8 9 8 8 9 8 8 9 8 8 9. Con N=12;M=5 emite 2 2 3 2 3. Con N=12;M=3 emite 4 4 ​​4.

Si los números de sección están basados ​​en 1 en lugar de en 0, la expresión es en su lugar (N*i)/M - (N*i-N)/M.

Answer 2

Las curvas de relleno de espacio y los fractales subdividen el plano y reducen la complejidad. Hay, por ejemplo, z-curve, hilbert curve, morton curve.