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

Учитывая массив с N элементами, я ищу M (M ‹ N) последовательных подмассивов с одинаковой длиной или с длинами, которые отличаются в основном на 1. Например, если N = 12 и M = 4, все подмассивы будут имеют одинаковую длину N/M = 3. Если N = 100 и M = 12, я ожидаю подмассивы с длинами 8 и 9, и оба размера должны быть равномерно распределены внутри исходного массива. Эта простая задача оказалась немного тонкой для реализации. Я придумал адаптацию алгоритма линии Брезенхэма, который выглядит так, если его закодировать в С++:

/// 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

Собственно вопрос в том, что я не знаю, как именно назвать свою проблему, поэтому с трудом искал.

  • Существуют ли другие алгоритмы для выполнения такой задачи?
  • Как они называются? Возможно, имена пришли бы, если бы я знал другие области применения.

Мне нужен был алгоритм как часть более крупного алгоритма кластеризации данных. Я думаю, что это также может быть полезно для реализации параллельной сортировки (?).


arrays algorithm uniform
person Angel Sinigersky    schedule 10.11.2011    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Если в вашем языке есть целочисленное деление, которое усекает, простой способ вычислить размер секции i — через (N*i+N)/M - (N*i)/M. Например, программа на питоне

  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.

person James Waldby - jwpat7    schedule 10.11.2011
comment
Следует отметить, что моя реализация, приведенная в вопросе, имеет дополнительную особенность: длины интервалов симметричны относительно середины массива. Для примера N = 100, M = 12 вы получите: 8 9 8 8 9 8 8 9 8 8 9 8 - person Angel Sinigersky; 11.11.2011

arrow_upward
0
arrow_downward

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

person Gigamegs    schedule 10.11.2011