用於將數組細分爲「半等號」，統一子數組的算法

給定一個包含N個元素的數組，我正在尋找M（M < N）個連續的子數組，其長度相同例如，如果N = 12且M = 4，則所有子陣列將具有相等的N/M = 3的長度。如果N = 100且M = 12，則我期望長度爲8和9的子陣列，以及兩種尺寸應該均勻分佈在原始陣列內。這個簡單的任務變得有點微妙的實施。我想出了Bresenham's line algorithm的適配，編碼在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 
}

此代碼計算間隔長度爲N = 100，M = 12：8 9 8 8 9 8 8 9 8 8 9 8

真正的問題是我不知道如何調用我的問題，所以我很難搜索它。

是否有其他算法來完成這樣的任務？
他們叫什麼名字？如果我知道其他應用領域，也許會出現這些名字。

我需要算法作爲更大的數據聚類算法的一部分。我認爲它也可以用於實現並行排序（？）。

來源

2011-11-10 Angel Sinigersky

如果您的語言具有截斷的整數除法，則計算i的大小的簡單方法是通過(N*i+N)/M - (N*i)/M。例如，Python程序

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

輸出號碼8 8 9 8 8 9 8 8 9 8 8 9. N=12;M=5它輸出2 2 3 2 3隨着N=12;M=3它輸出4 4 4

如果您的款號是基於1的而不是基於0的，則表示爲(N*i)/M - (N*i-N)/M。

來源

2011-11-10 18:24:39

簡單而好！謝謝！ –

應該指出，我在問題中給出的實現有一個額外的「特徵」：間隔長度相對於數組中間是「對稱的」。對於例子N = 100，M = 12，得到：8 9 8 8 9 8 8 9 8 8 9 8 –

空間填充曲線和分形可以細分飛機並降低複雜性。例如有z曲線，希爾伯特曲線，莫頓曲線。

來源

2011-11-10 18:25:30 Bytemain

用於將數組細分爲「半等號」，統一子數組的算法

回答

相關問題