|
|
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
Всем привет! Уважаемые гуру, подскажите, пжлста, возможно кто-то сталкивался с такой задачей. Условные данные: 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. Знаю, что на форуме неоднократно поднималась тема рюкзака и подобные задачи, однако я не нашел обсуждения вариантов решения вот такого множественного разбиения. Если ошибаюсь - подскажите ссылкой, пжлста. Спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 17:58 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
zipperxz Условные данные: данные желательно давать статичные, шоб проверять алгоритмы ..... stax ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 18:15 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 21:00 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
zipperxz Stax, исправил :) а желанный, результат? зы я ссилки не сохранаю, но постараюсь найти .... stax ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 21:37 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
Stax, желанный результат... Хм. Да собственно я вручную не подсчитывал наилучший результат, поэтому как таковых цифр нет) Чтобы данные по группам как можно равномернее были распределены) Знаю, что в данном случае можно использовать разностный алгоритм LDM, при котором на первом этапе значения заменяются их разностью, но хорошего описания данного метода для деления на множество групп, к сожалению, не нашел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 21:46 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
При этом требование такое - суммы по всем группам должны быть максимально равны. Суммы чего должны быть равны? Группы из одинакового количества значений? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2021, 23:27 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
Правильный Вася, нет, количество элементов в группах неважно, условно какая-то группа может и из одного элемента состоять. Условие именно на суммы значений элементов val в группе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2021, 08:53 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
zipperxz Буду раз людям подсказкам! Разделить количество бананов в упаковке по корзинам - buckets (SQL?) Разделить количество бананов в упаковке по корзинам - buckets (SQL?) Разделить количество бананов в упаковке по корзинам - buckets (SQL?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2021, 09:22 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
Elic, добрый день! Да, спасибо за ответ! Но, при всем уважении, мне кажется данный способ будет давать... средненький результат по равномерности распределения. При том что очевидный плюс, безусловно, его понятность и простота. Скажите, пжлста, а не было ли в практике использования одного из приемов, описанных в данной статье, т.е. ближе к эвристическим (надеюсь, корректно использовал это слово:))? Partition_problem ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2021, 17:52 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
zipperxz мне кажется данный способ будет давать... средненький результат по равномерности распределения {5,3,2,2,2,2} - крайне специфичный набор данных для двух кучек. В реальной жизни данные гораздо более стохастичны. Тем более, что ты не описываешь реальной задачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2021, 20:38 |
|
||
|
Partition problem
|
|||
|---|---|---|---|
|
#18+
Elic, Прошу прощения, не хотел обидеть :) Данные из реальной задачи привел, во втором сообщении. Возможно, и правда вчера недооценил твой способ. То есть создаем массивы по количеству групп, проходимся по значениям val из столбца, и раскидываем их по группам по условию наименьшей суммы в группе. Вцелом, такой алгоритм должен дать результат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2021, 09:02 |
|
||
|
|
start [/forum/topic.php?fid=52&msg=40123790&tid=1879635]: |
0ms |
get settings: |
15ms |
get forum list: |
8ms |
check forum access: |
1ms |
check topic access: |
1ms |
track hit: |
53ms |
get topic data: |
4ms |
get forum data: |
1ms |
get page messages: |
194ms |
get tp. blocked users: |
1ms |
| others: | 6ms |
| total: | 284ms |
| 0 / 0 |
