Algoritmo per la suddivisione di un array in sottosegmenti uniformi "semi-uguali"

Question

Dato un array con elementi N, sto cercando M (M < N) sotto-array successivi con lunghezze uguali o con lunghezze che differiscono per lo più 1. Ad esempio, se N = 12 e M = 4, tutti i sotto-array avranno le stesse lunghezze di N/M = 3. Se N = 100 e M = 12, mi aspetto sub-array con lunghezze 8 e 9, e entrambe le taglie dovrebbero essere distribuite uniformemente all'interno dell'array originale. Questo semplice compito si è rivelato un po 'sottile da implementare. Sono venuto con un adattamento del Bresenham's line algorithm, che appare così quando scritto in 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 
} 

Questo codice calcola le lunghezze di intervallo per N = 100, M = 12: 8 9 8 8 9 8 8 9 8 8 9 8

La vera domanda è che non so esattamente come chiamare il mio problema, quindi ho avuto difficoltà a cercarlo.

• Esistono altri algoritmi per eseguire tale compito?
• Come si chiamano? Forse i nomi verrebbero se conoscessi altre aree di applicazione.

Avevo bisogno dell'algoritmo come parte di un algoritmo più grande per il clustering di dati. Penso che potrebbe anche essere utile per implementare un ordinamento parallelo (?).

Answer 1

Se la tua lingua ha una divisione intera che tronca, un modo semplice per calcolare la dimensione della sezione i è tramite (N*i+N)/M - (N*i)/M. Ad esempio, il programma pitone

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

emette i numeri 8 8 9 8 8 9 8 8 9 8 8 9. Con N=12;M=5 emette 2 2 3 2 3. Con N=12;M=3 emette 4 4 ​​4.

Se i numeri di sezione sono basati su 1 anziché su 0, l'espressione è invece (N*i)/M - (N*i-N)/M.

Answer 2

Riempimento dello spazio: curve e frattali suddividono il piano e riducono la complessità. C'è per esempio curva z, curva hilbert, curva morton.