Fair distribution problem - T-SQL
 

Problem bih ja trebao rijesiti kroz T-SQL, ali bitnija mi je logika, pa bi ja oko nje mogao graditi query.

Radi se o slijedecem, koristit cu izmisljen scenarij.

Imam jednu veliku tablicu u kojoj se nalazi 1000 redova, sa dva stupca, ID i vrijednost.

Cilj je distribuirati ID-jeve u 5 skupina, na način da se u svakoj skupini nalazi podjednak broj ID-jeva, i da je ukupna vrijednost svake grupe opet podjednaka. Tolerancija je moguća, od nule pa do recimo 10%. Radi jednostavnosti, uzmimo da nema ekstrema u vrijednostima nego da su svi u range-u od recimo 100-500.

Ideje?

Hm, za*ebano :D
Mislim da je to prije "k-way (ili multiway) number partitioning problem" nego
"fair division".

Mislim da će ti tu t-sql biti veći problem od samog algoritma. Naime algoritmi postoje, treba ih samo implementirati, ali iterativni algoritmi, rekurzije ili pretraživanje stabla rješenja u sqlu mi ne zvuče primamljivo.
par linkova:
https://www.aaai.org/ocs/index.php/I...ewFile/625/705
https://www.aaai.org/ocs/index.php/I...File/3364/3574
http://www.mysmu.edu/faculty/kyriakos/IJCAI11.pdf
http://www.cs.uic.edu/pub/Isaim2014/..._Korf_etal.pdf

Dalje, za odabir algoritma je vrlo bitno koliko je tvoj izmišljeni scenarij izmišljen, a koliko stvaran. Tu prvenstveno mislim na broj particija. Da li će u praksi taj broj biti fiksan? Isto tako, toleranciju je teško garantirati. Eventualno sa nekim iterativnim algoritmom, da ne staje dok nije u tih 10%, ali i tu moraš često izmišljati nešto da ne zapneš u lokalnim ekstremima.

Evo našao sam i neki tekst o "bin packing" problemu u sql-u:
https://www.simple-talk.com/sql/t-sq...blems-the-sql/
koji bi mogao poslužiti.

"par minuta kasnije" ... :D
http://aprogrammerwrites.eu/?p=896
http://aprogrammerwrites.eu/?p=878
http://aprogrammerwrites.eu/?p=803

Ne odustaj, zadnji link je najbliže onom što ti treba. Idući koji nađeš će bit još bolji.

@OP, ne kuzim zasto bi se patio s necim ovakvim ako imas 1.000.000 redova, a kamo li 1.000...

To bi stvarno trebala biti bezobrazno ogromna i kompleksna tabela da se ubijas s necim ovakvim, barem IME na PgSQL.

Bubba ti si jedan od onih prodavača..
Ja kažem: "Imaš m6 maticu?"
On kaže: "Za šta ti treba?"

Malo ti je lose usporedba.

Moja percepcija je ta da ako je dosao na forum pitati za ovakvu nekakvu abominaciju, gotovo sigurno mu ili ne treba ili se moze odigrati jednostavnije. Nista vise.

A kao sto rekoh, primjer koji je dao je daleko od necega sto bi se povecano za redove velicine isplatilo zajebavati ovako.

Evo za pocetak, hvala na predlozenim linkovima, proucit cu to malo pa da vidim sto i kako.

Inace, ne radi se o "nepotrebnoj" stvari. Naime, na poslu imamo potrebu angažirati određene vanjske suradnike, no kako bi mogli procijeniti efikasnost svakog pojedinog, a bez da se bilo koji od njih "osjeća oštećen" radi toga što je dobio manje taskova, ili taskove manje vrijednosti, potrebno je te taskove "fairly" distribuirati.

Radi se o financijskom sektoru, tako da su i "fairly" i "taskovi" izraženi u nekoj valuti i iznosu koji je apsolutno usporediv s drugima (znaci termin koji sam koristio, "task manje vrijednosti" nije relativan i podlozan subjektivnoj procjeni).