Алгоритм разбиения массива на "полуравновешенные", равномерные подмассивы

Question

Учитывая массив с N элементами, я ищу M (M линейного алгоритма Брезенхэма, который выглядит так при кодировании на 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*i-N)/M,

Answer 2

Кривые заполнения пространства и фракталы делят плоскость и уменьшают сложность. Например, есть z-кривая, кривая Гильберта, кривая Мортона.