用于将数组细分为“半等于”均匀子阵列的算法

Given an array with N elements, I am looking for M (M < N) successive sub-arrays with equal lengths or with lengths that differ by mostly 1. For example, if N = 12 and M = 4, all sub-arrays would have equal lengths of N/M = 3. If N = 100 and M = 12, I expect sub-arrays with lengths 8 and 9, and both sizes should be uniformly spread within the original array. This simple task turned to be a little bit subtle to implement. I came up with an adaptation of the Bresenham's line algorithm, which looks like this when coded in C++:

给定一个包含N个元素的数组,我正在寻找M(M )个连续的子阵列,这些子阵列具有相同的长度或长度大多相差1的长度。例如,如果n>

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

This code calculates the interval lengths for N = 100, M=12: 8 9 8 8 9 8 8 9 8 8 9 8

该代码计算N = 100的间隔长度,M = 12:8 9 8 8 9 8 8 9 8 8 9 8

The actual question is that I don't know how exactly to call my problem, so I had difficulty searching for it.

实际的问题是,我不知道如何调用我的问题,所以我很难找到它。

Are there other algorithms for accomplishing such a task?

是否有其他算法来完成这样的任务?

How are they called? Maybe the names would come if I knew other areas of application.

他们怎么称呼?如果我知道其他应用领域,也许名字会来。

I needed the algorithm as a part of a bigger algorithm for clustering of data. I think it could also be useful for implementing a parallel sort(?).

我需要将算法作为更大算法的一部分来进行数据聚类。我认为它对于实现并行排序(?)也很有用。

2 个解决方案

#1

If your language has integer division that truncates, an easy way to compute the size of section i is via (N*i+N)/M - (N*i)/M. For example, the python program

如果你的语言有截断的整数除法,计算段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

outputs the numbers 8 8 9 8 8 9 8 8 9 8 8 9. With N=12;M=5 it outputs 2 2 3 2 3. With N=12;M=3 it outputs 4 4 4.

输出数字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。

If your section numbers are 1-based rather than 0-based, the expression is instead (N*i)/M - (N*i-N)/M.

如果您的区段编号是基于1而不是基于0,则表达式是(N * i)/ M - (N * i-N)/ M.

#2

Space-filling-curves and fractals subdivide the plane and reduce the complexity. There is for example z-curve, hilbert curve, morton curve.

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

#1