将数组细分为“半相等”、均匀子数组的算法

Question

给定一个包含 N 个元素的数组，我正在寻找 M (M < N) 个长度相等或长度相差大部分为 1 的连续子数组。例如，如果 N = 12 且 M = 4，则所有子数组将具有相等的长度 N/M = 3。如果 N = 100 且 M = 12，我期望长度为 8 和 9 的子数组，并且这两个大小应在原始数组中均匀分布。这个简单的任务实施起来有点微妙。我提出了 Bresenham 线算法的改编版，在编码时看起来像这样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实际的问题是我不知道如何准确地称呼我的问题，所以我很难找到它。

• 还有其他算法可以完成这样的任务吗？
• 他们怎么称呼？如果我知道其他应用领域，也许这些名字就会出现。

我需要该算法作为更大的数据聚类算法的一部分。我认为它对于实现并行排序也很有用（？）。

Answer 1

如果您的语言具有截断的整数除法，则计算部分 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*iN)/M。

Answer 2

空间填充曲线和分形细分平面并降低复杂性。例如有 z 曲线、希尔伯特曲线、莫顿曲线。