The Partition Problem
http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM#SECTION02312000000000000000
Suppose that three workers are given the task of scanning through a shelf of books in search of a given piece of information. To get the job done fairly and efficiently, the books are to be partitioned among the three workers. To avoid the need to rearrange the books or separate them into piles, it would be simplest to divide the shelf into three regions and assign each region to one worker.
But what is the fairest way to divide the shelf up? If each book is the same length, say 100 pages, the job is pretty easy. Just partition the books into equal-sized regions,
100 100 100 | 100 100 100 | 100 100 100
so that everyone has 300 pages to deal with.
But what if the books are not the same length? Suppose we used the same partition when the book sizes looked like this:
100 200 300 | 400 500 600 | 700 800 900 |
I, for one, would volunteer to take the first section, with only 600 pages to scan, instead of the last one, with 2,400 pages. The fairest possible partition for this shelf would be
100 200 300 400 500 | 600 700 | 800 900
where the largest job is only 1,700 pages and the smallest job 1,300.I asked a similar question here https://www.mapleprimes.com/questions/200480-Product-Groupingthe difference here being the split up into groups of 5,2 and 2 rather than nominating 3 groups of 3.Joe Riels Iterator:-RevolvingDoorCombination may the way to go, but that was concerned with spliting two lists, minimizing the difference of their sums.Is it possible for code to detect the best 3 way splitup, rather than nominating the combination of:groups [1,1,7],[2,2,5], [2,3,4],[3,3,3]Anyway here are Yuri's (for 3 x 3) and Joes Codesrestart:
ts := time():
S := {seq(100..900,100)}: Var := infinity:
T := combinat[choose](S, 3):
for t in T do
S1 := `minus`(S, t):
U := combinat[choose](S1, 3):
for u in U do
S2 := `minus`(S1, u):
Var1 := abs(convert(t, `*`)-convert(u, `*`))+abs(convert(u, `*`)-convert(S2, `*`))+abs(convert(t, `*`)-convert(S2, `*`)):
if Var1 < Var then Var := Var1:
L := {Var, {S2, t, u}} end if
end do end do:
L;
time()-ts;
restart:
MinVal := proc(p :: Array(datatype=integer[4]) , lg :: Array(datatype=float[8]) , pmin :: Array(datatype=integer[4]) , m :: float , K :: float , n :: posint , len :: posint )local i,j,v,x; v := 0.0; for i from 0 to n-1 by len do x := 0.0; for j to len do x := x + lg[p[i+j]]; end do; v := v + abs(x - K); end do; # test for minimum if m <= v then v := m; else # update pmin for i to n do pmin[i] := p[i]; end do; end if; return v;end proc:Var := proc(L::list(positive) , len :: posint , num :: posint )local M, P, i, j, K, lg, n, p, pmin; n := numelems(L); if len*num <> n then error "invalid partition specification"; end if; # allocate arrays used by MinVal pmin := Array(1..n, 'datatype'=integer[4]); lg := Array(evalf(ln~(L)),'datatype'=float[8]); K := add(i, i=lg)/num; M := K*len; P := Iterator:-SetPartitions(n,[[len,num]],'transformer=permute'); for p in P do M := MinVal(p, lg, pmin, M, K, n, len); end do; return ListTools:-LengthSplit(convert(pmin,list), len);end proc:L:=[seq(100..900,100)]:
MinVal := Compiler:-Compile(MinVal):CodeTools:-Usage((Var)(L, 5,2));