时间戳

首页 > 解决方案 > php算法将一组数据分成不超过四个的组

php - php算法将一组数据分成不超过四个的组

问题描述

我目前有一个问题，我有一个大约1000 个条目的数据集。

每个条目都有两个相关的特征：

我必须将这些条目分成最大组。四个条目。但是，组可以包含更少的条目。

现在，这些条目被分类到组中的方式取决于它们的特征，如下所示：

数据集中weight的范围大约为20.0到120.0。大约有50种不同的可能值origin。

我必须在 php 中实现这一点，但不需要用 php 实现来回答。单独的算法就足够了。

我尝试为它们的所有值排序weight，然后每隔四个条目简单地拆分它们。但是我得到的组很难根据origin价值重新排列。我想我可以通过一个讨厌的实现以某种方式完成这件事，但我希望有一个非常优雅的算法可以做到这一点。

提前致谢！

标签： phpalgorithmsorting

解决方案

这是一个可能会产生良好结果的贪心：

Sort entried by weight
groups = []
used = array of length len(entries) initialized in false    
For i = 0 to len(entries):
    if (used[i] == false):
        group = [entries[i]]
        j = i + 1
        while(j < len(entries) and delta(group[0], entries[j]) < 10 and len(group) < 4):
           if used[j] == false and entries[j].origin != all the origins in group:
               group.add(entries[j])
               used[j] = true
           j = j + 1
        if (len(group) < 4):
            //decide if you prefer a small group or a bigger group with repeated origins
        groups.add(group)

推荐阅读