алгоритм php, сортирующий набор данных по группам не более четырех

Question

В настоящее время у меня проблема с тем, что у меня есть набор данных около 1000 записей.

Каждая запись имеет две соответствующие функции:

• weight (число с плавающей запятой)
• origin (строка / другая сущность)

Я должен отсортировать эти записи по группам макс. четыре записи. Группы могут содержать меньше записей.

• группа из четырех записей: очень хорошо
• группа из трех записей: хорошо
• группа из двух записей: не очень хорошо
• группа из одной записи: действительно плохо (но возможно, если не избежать)

Теперь способ сортировки этих записей в группах зависит от их функций следующим образом:

• макс. дельта weight внутри группы может составлять 10% .
• должно быть столько разных значений для origin, сколько возможно в каждой группе. Наличие одного дубликата не так уж и плохо, но следует избегать трех или более записей с одинаковым origin.

В наборе данных weight имеет диапазон примерно от 20.0 до 120.0 . Существует около 50 различных возможных значений для origin.

Я должен реализовать это в php, но не нужно отвечать реализацией php. Одного алгоритма будет достаточно.

Я попытался отсортировать все значения по их weight, а затем просто разделил их на каждую четвертую запись. Но группы, которые я тогда получаю, трудно переставить с учетом значения origin. Я думаю, что я мог бы как-то сделать это с помощью неприятной реализации, но я надеюсь, что есть очень элегантный алгоритм, который может сделать это.

Заранее спасибо!

Answer 1

Вот жадный, который может дать хорошие результаты:

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)