Help:=proc(): print(`Delta1(X), AntiDelta1(L), Test(n) `):
print(` minusL(L1,L2), MinusL1(L,a), Children(XL,w) `):
print(`Descendants(XL,width), PDP(L) , TestPDP(L)`):
end:

with(combinat):

#Delta1(X): the sorted list of differences of a sorted
#list of integers
Delta1:=proc(X):

sort([seq(seq(X[j]-X[i],i=1..j-1),j=1..nops(X))]):

end:

#Test(n): Tests AntiDelta1 for sequenes of length n
Test:=proc(n) local L,X,i,ra:ra:=rand(1..10^10);
X:=sort([0,seq(ra(),i=1..n-1)]);
 L:=Delta1(X):
 member(X,AntiDelta1(L)):
 end:

#AntiDelta1(L): Given a sorted list of integers L, 
#tries to find a sorted list X, such that Delta1(X)=L
#For example AntiDelta1([1,5,6]); or returns FAIL
AntiDelta1:=proc(L) local X,N,n,L1, S,BigGuy,i,T:

N:=nops(L):
BigGuy:=L[nops(L)]:

n:=max(solve(n*(n-1)/2=N)):

if not type(n,integer) then
 print(`Length of input list is not a triangular number`):
  RETURN(FAIL):
fi:

L1:=[op(1..N-1,L)]:

S:=choose(L1,n-2):

S:={seq([0, op(S[i]), BigGuy],i=1..nops(S))}:

T:={}:

for i from 1 to nops(S) do
 
X:=S[i]:

if Delta1(X)=L then
    T:=T union {X}:
fi:
od:

T:

end:


#Test(n): Tests AntiDelta1 for sequenes of length n
Test:=proc(n) local L,X,i,ra:ra:=rand(1..10^10);
X:=sort([0,seq(ra(),i=1..n-1)]);
 L:=Delta1(X):
 member(X,AntiDelta1(L)):
 end:


#minusL(L1,L2): the list L1 minus the list L2 or
#FAIL
minusL:=proc(L1,L2) local i,L:

L:=L1:
for i from 1 to nops(L2) do
 L:=minusL1(L,L2[i]):
  
   if L=FAIL then
      RETURN(FAIL):
   fi:
od:
L:
end:

#minusL1(L,a): removes the element a from L
#(if a belongs to L), or returns FAIL
minusL1:=proc(L,a) local i, Avi:

Avi:=nops(L):
for i from  1 to Avi do
 if L[i]=a then
  break:
 fi:
od:

if i=Avi+1 then 
 FAIL:
else
 [op(1..i-1,L),op(i+1..Avi,L)]:
fi:

end:

#Children(XL,width): Given a pair [X,L] of partial
#output X and not yet accounted distances L.
#and a number w (the width)
#outputs the two children
Children:=proc(XL,w) local X,L,y,X1,L1,NewD,S:
X:=XL[1]: L:=XL[2]:

if L=[] then
 RETURN({}):
fi:

S:={}:

y:=L[nops(L)]:
X1:=sort([y, op(X)]):

NewD:=sort([seq(abs(X[i]-y), i=1..nops(X))]):

L1:=minusL(L,NewD):

if L1<>FAIL then
 S:=S union {[X1,L1]}:
fi:

y:=w-L[nops(L)]:
X1:=sort([y, op(X)]):

NewD:=sort([seq(abs(X[i]-y), i=1..nops(X))]):

L1:=minusL(L,NewD):

if L1<>FAIL then
 S:=S union {[X1,L1]}:
fi:

S:

end:


#Descendants(XL,width): all the good descendants with
#empty second component
Descendants:=proc(XL,width)
local C,S,i:
if XL[2]=[] then
   RETURN({XL[1]}):
fi:

C:=Children(XL,width):

S:={}:

for i from 1 to nops(C) do

S:=S union Descendants(C[i],width):
od:

S:

end:

#PDP(L): Given a sorted list of integers L, 
#tries to find a sorted list X, such that Delta1(X)=L
#For example PDP([1,5,6]); or returns FAIL
PDP:=proc(L) local X1,N,n,L1, S,BigGuy:

N:=nops(L):
BigGuy:=L[nops(L)]:

n:=max(solve(n*(n-1)/2=N)):

if not type(n,integer) then
 print(`Length of input list is not a triangular number`):
  RETURN(FAIL):
fi:

X1:=[0,BigGuy]:
L1:=[op(1..nops(L)-1,L)]:
Descendants([X1,L1],BigGuy):

end:



#TestPDP(n): Tests PDP for sequenes of length n
TestPDP:=proc(n) local L,X,i,ra:ra:=rand(1..10^10);
X:=sort([0,seq(ra(),i=1..n-1)]);
 L:=Delta1(X):
 member(X,PDP(L)):
 end: