Гость
Map
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Partition problem / 11 сообщений из 11, страница 1 из 1
28.12.2021, 17:58
    #40123671
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Всем привет!

Уважаемые гуру, подскажите, пжлста, возможно кто-то сталкивался с такой задачей.
Условные данные:

with t as (
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual union all
select trunc(10000 * dbms_random.value) val, ' ' as grp from dual
)
select * from t


Задача - требуется расставить всем значениям val номер группы в столбец grp (от 1 до 8). При этом требование такое - суммы по всем группам должны быть максимально равны. То есть нужно максимально равномерно распределить данные по группам.
Я хотел решить это с помощью алгоритма Кармаркара-Карпа, он же LDM, но внезапно понял, что не до конца представляю как этот алгоритм работает для множества групп и как на втором этапе происходит восстановление партиций после первого этапа, где числа последовательно заменяются разностью, и что еще более непонятно - как это реализовать на sql/plsql.
Буду раз людям подсказкам! P.S. задачу пытаюсь решить либо на SQL, либо pl/sql.

Знаю, что на форуме неоднократно поднималась тема рюкзака и подобные задачи, однако я не нашел обсуждения вариантов решения вот такого множественного разбиения. Если ошибаюсь - подскажите ссылкой, пжлста. Спасибо!
...
Рейтинг: 0 / 0
28.12.2021, 18:15
    #40123675
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
zipperxz

Условные данные:

данные желательно давать статичные, шоб проверять алгоритмы

.....
stax
...
Рейтинг: 0 / 0
28.12.2021, 21:00
    #40123722
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Stax, исправил :)


with t as (
select 842854 as val, ' ' as grp from dual union all
select 223635 as val, ' ' as grp from dual union all
select 792677 as val, ' ' as grp from dual union all
select 982181 as val, ' ' as grp from dual union all
select 729349 as val, ' ' as grp from dual union all
select 427755 as val, ' ' as grp from dual union all
select 572896 as val, ' ' as grp from dual union all
select 921370 as val, ' ' as grp from dual union all
select 47618 as val, ' ' as grp from dual union all
select 836077 as val, ' ' as grp from dual union all
select 623391 as val, ' ' as grp from dual union all
select 235966 as val, ' ' as grp from dual union all
select 676862 as val, ' ' as grp from dual union all
select 643398 as val, ' ' as grp from dual union all
select 125684 as val, ' ' as grp from dual union all
select 179640 as val, ' ' as grp from dual union all
select 719781 as val, ' ' as grp from dual union all
select 872850 as val, ' ' as grp from dual union all
select 978958 as val, ' ' as grp from dual union all
select 960144 as val, ' ' as grp from dual union all
select 88590 as val, ' ' as grp from dual union all
select 830416 as val, ' ' as grp from dual union all
select 689889 as val, ' ' as grp from dual union all
select 798929 as val, ' ' as grp from dual union all
select 707491 as val, ' ' as grp from dual union all
select 766289 as val, ' ' as grp from dual union all
select 193738 as val, ' ' as grp from dual union all
select 382435 as val, ' ' as grp from dual union all
select 407950 as val, ' ' as grp from dual union all
select 398201 as val, ' ' as grp from dual
) select * from t
...
Рейтинг: 0 / 0
28.12.2021, 21:37
    #40123726
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
zipperxz
Stax, исправил :)

а желанный, результат?

зы
я ссилки не сохранаю, но постараюсь найти

....
stax
...
Рейтинг: 0 / 0
28.12.2021, 21:46
    #40123727
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Stax,

желанный результат... Хм. Да собственно я вручную не подсчитывал наилучший результат, поэтому как таковых цифр нет)
Чтобы данные по группам как можно равномернее были распределены)
Знаю, что в данном случае можно использовать разностный алгоритм LDM, при котором на первом этапе значения заменяются их разностью, но хорошего описания данного метода для деления на множество групп, к сожалению, не нашел.

LDM
...
Рейтинг: 0 / 0
28.12.2021, 23:27
    #40123745
Правильный Вася
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
При этом требование такое - суммы по всем группам должны быть максимально равны.
Суммы чего должны быть равны? Группы из одинакового количества значений?
...
Рейтинг: 0 / 0
29.12.2021, 08:53
    #40123790
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Правильный Вася,
нет, количество элементов в группах неважно, условно какая-то группа может и из одного элемента состоять.
Условие именно на суммы значений элементов val в группе.
...
Рейтинг: 0 / 0
29.12.2021, 09:22
    #40123795
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
...
Рейтинг: 0 / 0
29.12.2021, 17:52
    #40124025
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Elic,

добрый день!
Да, спасибо за ответ!
Но, при всем уважении, мне кажется данный способ будет давать... средненький результат по равномерности распределения. При том что очевидный плюс, безусловно, его понятность и простота.
Скажите, пжлста, а не было ли в практике использования одного из приемов, описанных в данной статье, т.е. ближе к эвристическим (надеюсь, корректно использовал это слово:))?

Partition_problem
...
Рейтинг: 0 / 0
29.12.2021, 20:38
    #40124056
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
zipperxz
мне кажется данный способ будет давать... средненький результат по равномерности распределения
Перекрестись. Чем меряешь "средненькость"?
{5,3,2,2,2,2} - крайне специфичный набор данных для двух кучек. В реальной жизни данные гораздо более стохастичны.
Тем более, что ты не описываешь реальной задачи.
...
Рейтинг: 0 / 0
30.12.2021, 09:02
    #40124103
zipperxz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Partition problem
Elic,
Прошу прощения, не хотел обидеть :)
Данные из реальной задачи привел, во втором сообщении.
Возможно, и правда вчера недооценил твой способ.
То есть создаем массивы по количеству групп, проходимся по значениям val из столбца, и раскидываем их по группам по условию наименьшей суммы в группе.
Вцелом, такой алгоритм должен дать результат
...
Рейтинг: 0 / 0
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Partition problem / 11 сообщений из 11, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]