Как разделить список чисел на группы по заданному расстоянию между числами в группе?
Всем привет. Нужен совет как правильно (не правильно/не красиво и т.д. придумать могу) сделать следующее:
На вход подается список/массив/множество (без разницы) чисел (какие-либо данные)
25,0 27,04 27,04 26,4 27,08 27,04 27 27 26,95 26,91
И число Х - погрешность , как правильно назвать ее не знаю, сорри)))
На выходе нужно получить группы:
(27,04 27,04 27,08 27,04 27 27 26,95 26,91) (26,4) (25,0).
Есть идея: число Х задает погрешность куда попадает текущее число, т.е.
Берем число 25,0 (К) - группа будет К+Х и К-Х - если число Х = 5, то в группу попадают числа от 24,95 до 25,05.
Да вопрос связан с математикой (не силен в ней:)), похоже на какое-то разбиение, .
Прошу совета как это правильно сделать (правильный алгоритм)!! Параллельно думаю как это сделать.
Любую критику принимаю)!!
Задачка , так из так сказать pet-проекта на досуге))!
Заранее всем спасибо за потраченное время на мой вопрос!!
Никакой "математики" тут нет. Впрочем, как и кластерного анализа. Все тривиально просто. Если все именно так, как вы описали, то вы собственно уже сами и описали ваш алгоритм. Правда опустив первый его шаг - предварительную сортировку.
Итак:
1. Сортируем имеющиеся данные.
2. Начинаем просмотр (не важно с какого -верхнего или нижнего) крайнего члена последовательности и сравниваем следующий элемент последовательности с границей вашего интервала (кстати - в вопросе, наверное, ошибка, и Х у вас не 5, а 0.05). Соответственно, включаем его в первую группу, или "закрываем" первую группу и переходим к формированию второй. Повторяем это действие циклически перебирая последовательно все элементы нашего отсортированного набора.
Если попытаться обойтись без предварительной сортировки - что в принципе тоже не очень сложно - то надо аккуратно посмотреть, не увеличится-ли при этом вычислительная сложность (на вскидку я в этом не уверен).
Да, еще нужно подумать над определением что входит в группу (границы брать/не брать, может еще какие-то условия) но это уже оптимизация, наверное)))!.
Но мне кажется что сортировка - дополнительная работа, или я что-то не понимаю))!
Спасибо за ваш комментарий.
Сделал с Map>, где String - key = 23.95-24.05, List = 24 24.
Таким образом за один проход получил, вроде, то что хотел))!
Только значение ключа пока-что не сильно нравится, может что-то придумаю еще.))
Alex Fox, Если без сортировки, то попробуйте обработать массив, например:
25.6 23.5 24.5 26.8 24.6 24 25 25.3 24 - сделать можно, но вычислительная сложность стала больше. Так что лишнее делать сортировку или нет - думайте сами.
P.S. Как человеку новому на этом форуме подскажу - "Спасибо" тут выражается несколько иначе.
