fxDistribute – немножко решения задач оптимизации на М
#АнатомияФункций – custom
Всем привет!
Я упорно не пытаюсь решать задачи оптимизации на М, но они упорно возникают в чате. Поэтому, раз уж поддержали пост, решаем задачу:
на вход подаётся список из N позиций с указанием их «веса», список нужно разделить на M равных (почти равных если целочисленное деление невозможно) групп с максимально равной суммой весов. Ок, у меня вышло примерно так:
По шагам:
n – определяем общую длину списка, чтобы делилось поровну
sort – дополняем список до нужной длины нулями и сортируем
av – находим среднее по списку
tr – преобразуем фактические веса в величину отклонения от среднего
zip – нарезаем список по N элементов и получаем M достаточно одинаковых групп – опорный план
теперь немножко перескочим
gen – итеративно применяем к полученным спискам функцию f и следим за остаточной суммой отклонений – продолжаем пока она уменьшается
tbl -результат последней итерации превращаем в таблицу
to – возвращаем «весам» их первозданный вид
Теперь по функции f – реализованный алгоритм ищет локальный минимум – это важно, потому как решил не усложнять жизнь ни себе, ни оперативе.
tst, last, sum1, sum2,l st1, lst2 – находим группы с наибольшей (положительной) и наименьшей (отрицательной) суммами
cr, lst – находим все сочетания элементов этих двух групп и как их обмен повлияет на общий результат
slct – выбираем наиболее подходящую пару
new – осуществляем обмен элементами между группами
Как-то так. Поиск локального минимума не всегда оптимален, зато работает шустро и пишется просто )))
Надеюсь, было полезно.
Всех благ!
@buchlotnik
#АнатомияФункций – custom
Всем привет!
Я упорно не пытаюсь решать задачи оптимизации на М, но они упорно возникают в чате. Поэтому, раз уж поддержали пост, решаем задачу:
на вход подаётся список из N позиций с указанием их «веса», список нужно разделить на M равных (почти равных если целочисленное деление невозможно) групп с максимально равной суммой весов. Ок, у меня вышло примерно так:
(lst,num)=>
let
n=Number.RoundUp(List.Count(lst)/num)*num,
sort = List.Sort(lst&List.Repeat({0},n-List.Count(lst))),
av=List.Average(sort),
tr=List.Transform(sort,(x)=>x-av),
zip = List.Zip(List.Split(tr,num)),
f=(base)=>
[tst=List.Buffer(List.Sort(base,(x)=>List.Sum(x))),
last=List.Last(tst),
sum1=Number.Abs(List.Sum(tst{0})),
sum2=Number.Abs(List.Sum(last)),
lst1=if sum2>sum1 then tst{0} else last,
lst2=if sum2>sum1 then last else tst{0},
cr=List.Sum(lst2),
lst=List.TransformMany(lst2,(x)=>lst1,(x,y)=>{x,y,cr-x+y}),
slct= if cr <0
then List.Max(List.Select(lst,(x)=>x{2}<0),null,(x)=>x{2})
else List.Min(List.Select(lst,(x)=>x{2}>0),null,(x)=>x{2}),
f=(x,y,z)=>List.ReplaceRange(x,List.PositionOf(x,y),1,{z}),
new={f(lst2,slct{0},slct{1})}&List.Range(tst,1,num-2)&{f(lst1,slct{1},slct{0})}][new],
gen=List.Generate(()=>[i=0,l=zip,s=List.Sum(List.Transform(l,(x)=>Number.Abs(List.Sum(x)))),fl=true],(x)=>x[fl],
(x)=>[i=x[i]+1,l=f(x[l]),s=List.Sum(List.Transform(l,(x)=>Number.Abs(List.Sum(x)))),fl=s<x[s]],
(x)=>x[l]),
tbl = Table.FromColumns(List.Last(gen)),
to=Table.TransformColumns(tbl,{},(x)=>x+av)
in
to
По шагам:
n – определяем общую длину списка, чтобы делилось поровну
sort – дополняем список до нужной длины нулями и сортируем
av – находим среднее по списку
tr – преобразуем фактические веса в величину отклонения от среднего
zip – нарезаем список по N элементов и получаем M достаточно одинаковых групп – опорный план
теперь немножко перескочим
gen – итеративно применяем к полученным спискам функцию f и следим за остаточной суммой отклонений – продолжаем пока она уменьшается
tbl -результат последней итерации превращаем в таблицу
to – возвращаем «весам» их первозданный вид
Теперь по функции f – реализованный алгоритм ищет локальный минимум – это важно, потому как решил не усложнять жизнь ни себе, ни оперативе.
tst, last, sum1, sum2,l st1, lst2 – находим группы с наибольшей (положительной) и наименьшей (отрицательной) суммами
cr, lst – находим все сочетания элементов этих двух групп и как их обмен повлияет на общий результат
slct – выбираем наиболее подходящую пару
new – осуществляем обмен элементами между группами
Как-то так. Поиск локального минимума не всегда оптимален, зато работает шустро и пишется просто )))
Надеюсь, было полезно.
Всех благ!
@buchlotnik