gpt4 book ai didi

将数组分割为 "semi-equal"统一子数组的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:46:28 30 4
gpt4 key购买 nike

给定一个包含 N 个元素的数组,我正在寻找 M (M < N) 个长度相等或长度相差大部分为 1 的连续子数组。例如,如果 N = 12 且 M = 4,则所有子数组-arrays 将具有 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

实际的问题是我不知道如何准确地称呼我的问题,所以我很难搜索它。

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

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

最佳答案

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

关于将数组分割为 "semi-equal"统一子数组的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8084010/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com