:

## Cutting problem (2 procedures)

This post - this is a generalization of the question from  here .
Suppose we have  m  divisible objects that need to be divided equally between n persons, and so that the total number of parts (called  N  in the text of the procedure) after cutting should be a minimum. Cutting procedure exactly solves this problem. It can be proved that the estimate holds  n<=N<=n+m-1, and  N<n+m-1 if and only if there are several objects (< m), whose measures sum to be a multiple of the share (Obj in the text of the procedure).

In the attached file you can find also the text of the second procedure Cutting1, which is approximately solves the problem. The procedure Cutting1 is much faster than Cutting. But the results of their work are usually the same or Cutting procedure gives a slightly better result than Cutting1.

Required parameters of the procedure: L is the list of the measures of the objects to be cutted, n is the number of persons. The optional parameter  Name is a name or the list of names of the objects of L (if the latter then should be nops(L)=nops(Name) ).

Cutting:=proc(L::list(numeric), n::posint, Name::{name,list(name)}:=Object)

local m, n1, L1, L11, mes, Obj, It, M, N;

uses combinat, ListTools;

m:=nops(L); L1:=sort([seq([`if`(Name::name,Name||i,Name[i]),L[i]], i=1..m)], (a,b)->a[2]<=b[2]);

mes:=table(map(t->t[1]=t[2],L1));

Obj:=`+`(L[])/n;

It:=proc(L1, n)

local i, M, m1, S, n0, a, L2;

if nops(L1)=1 then return [[[L1[1,1],Obj]] \$ n] fi;

if n=1 then return [L1] fi;

for i from 1 while `+`(seq(L1[k,2],k=1..i))<=Obj do

od;

M:=[seq(choose(L1,k)[], k=1..ceil(nops(L1)/2))];

S:=[];

for m1 in M while nops(S)=0 do n0:=`+`(seq(m1[k,2],k=1..nops(m1)))/Obj;

if type(n0,integer) then S:=m1 fi;

od;

if nops(S)=0 then

a:=Obj-`+`(seq(L1[k,2],k=1..i-1));

L2:=[[L1[i,1],L1[i,2]-a],seq(L1[k],k=i+1..nops(L1))];

[[seq(L1[k], k=1..i-1),`if`(a=0,NULL,[L1[i,1],a])],It(L2,n-1)[]] else L2:=sort(convert(convert(L1,set) minus convert(S,set), list),(a,b)->a[2]<=b[2]);

[It(S,n0)[], It(L2,n-n0)[]] fi;

end proc;

M:=It(L1,n);

N:=add(nops(M[i]), i=1 ..nops(M));

Flatten(M, 1);

[Categorize((a,b)->a[1]=b[1],%)];

print(``);

print(cat(`Cutting scheme (total  `, N, `  parts):`) );

print(map(t->[seq(t[k,2]/`+`(seq(t[k,2],k=1..nops(t)))*t[1,1],k=1..nops(t))], %)[]);

print(``);

print(`Scheme of sharing out:`);

seq([Person||k,`+`(seq(M[k,i,2]/mes[M[k,i,1]]*M[k,i,1], i=1..nops(M[k])))],k=1..n);

end proc:

Examples of use.

First example from the link above:

Cutting([225,400,625], 4, Cake);  # 3 cakes must be equally divided by 4 persons

eval(%,[Cake1,Cake2,Cake3]=~[225,400,625]);  # Check

Second example (the same for 10 persons):

Cutting([225,400,625], 10, Cake);

Third example (7 identical apples should be divided between 12 persons):

Cutting([1 \$ 7], 12, apple);

Edited:

1. Fixed a bug in the procedure Cutting  (I forgot sort the list  L2  in sub-procedure  It  if  nops(S)<>0 ).

2. Changes made to the sub-procedure  It  for the case if there are several objects (>1  and  < m), whose measures                     sum to be a multiple of the share  Obj .

﻿