Find an array that fits a set of sums

Question

Consider an array A of length n. The array contains only positive integers. For example A = (1,1,2,2). Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}. The steps to produce f(A) are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

Task

Given a set of sums S given in sorted order containing only positive integers and an array length n, your task is to output at least one array X such that f(X) = S.

For example, if S = {1,2,3,5,6} and n = 3 then a valid output is X = (1,2,3).

If there is no such array X your code should output any constant value.

Examples

Input: n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13), possible output: X = (3, 5, 1, 4)

Input: n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22), possible output: X = (5, 3, 2, 2, 5, 5)

Input: n=6, S = (2, 4, 6, 8, 10, 12, 16), possible output: X = (4, 2, 2, 2, 2, 4)

Input: n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14), possible output: X = (4, 2, 1, 1, 2, 4)

Input: n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25), possible output: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Input: n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31), possible output: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Input and output format

Your code can take input and give output in any easily human read format you find convenient. However, please show the output of testing it on the examples in the question.

Running time

You must be able to run the code to completion for all the examples in the question. It should in principle be correct for n up to 15 but you do not need to prove it would be fast enough for all inputs.

Answer 1

Husk, 20 bytes

ḟȯ⁰¦ṁ∫ṫ!¡Sof~Λ€∫×:¹g

Try it online!

Returns one solution, or an empty list if it doesn't exist. The last test case (n=15) finishes in 3.8 seconds on TIO.

Explanation

The program has two parts. In the first part (¡ and to the right of it), we construct an infinite list whose kth element is a list containing all length-k lists whose slice sums are in S. We do this inductively, starting from the 1-element slices of S, and at each step prepending each element of S to each list, and keeping those whose prefix sums are in S. In the second part (! and to the left of it), we take the nth element of the list, which contains length-n lists. Of these, we select the first one whose slice sums actually contain every element of S.

In the code, let's first replace o and ȯ (which compose two and three functions into one) by parentheses for clarity.

¡S(f~Λ€∫)×:¹g  First part. Input is a list, say S=[1,2,3]
            g  Group equal adjacent elements: [[1],[2],[3]]
¡              Iterate function:
                Argument is a list of lists, say [[1,1],[1,2],[2,1]]
         ×      Mix (combine two lists in all possible ways)
          :     by prepending
           ¹    with the list S: [[1,1,1],[1,1,2],[2,1,1],[1,2,1],[2,1,2],[3,1,1],[2,2,1],[3,1,2],[3,2,1]]
   f            Filter by condition:
        ∫        Cumulative sums: [[1,2,3],[1,2,4],[2,3,4],[1,3,4],[2,3,5],[3,4,5],[2,4,5],[3,4,6],[3,5,6]]
     ~Λ          All of the numbers
 S     €         are elements of S: [[1,1,1]]
                 Only this list remains, since the other cumulative sums contain numbers not from S.
               Result of iteration: [[[1],[2],[3]],[[1,1],[1,2],[2,1]],[[1,1,1]],[],[],[]...

ḟ(⁰¦ṁ∫ṫ)!      Second part. Implicit input, say n=2.
        !      Take nth element of above list: [[1,1],[1,2],[2,1]]
ḟ              Find first element that satisfies this:
                Argument is a list, say [1,2]
      ṫ         Tails: [[1,2],[2]]
    ṁ           Map and concatenate
     ∫          cumulative sums: [1,3,2]
 ȯ ¦            Does it contain all elements of
  ⁰             S? Yes.
               Result is [1,2], print implicitly.

There are some parts that need more explanation. In this program, the superscripts ⁰¹ both refer to the first argument S. However, if α is a function, then α¹ means "apply α to S", while ⁰α means "plug S to the second argument of α". The function ¦ checks whether its first argument contains all elements of the second (counting multiplicities), so S should be its second argument.

In the first part, the function that ¡ uses can be interpreted as S(f~Λ€∫)(×:)¹. The combinator S behaves like Sαβγ -> (αγ)(βγ), which means that we can simplify it to (f~Λ€∫¹)(×:¹). The second part, ×:¹, is "mix with S by prepending", and its result is passed to the first part. The first part, f~Λ€∫¹, works like this. The function f filters a list by a condition, which in this case is ~Λ€∫¹. It receives a list of lists L, so we have ~Λ€∫¹L. The combinator ~ behaves like ~αβγδε -> α(βδ)(γε): the first argument is passed to β, the second to γ, and the results are combined with α. This means that we have Λ(€¹)(∫L). The last part ∫L is just the cumulative sums of L, €¹ is a function that checks membership in S, and Λ takes a condition (here €¹) and a list (here ∫L), and checks that all elements satisfy it. Put simply, we filter the results of the mixing by whether their cumulative sums are all in S.

Answer 2

Ruby, 135 bytes

->a,n{r=w=1;r+=1until w=(s=a[0,r]).product(*[s]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Try it online!

Use a breadth-first search. n=10 works on TIO, n=15 takes longer than a minute, but works on my machine.

Ruby, 147 bytes

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product(*[s=a[0,r]]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Try it online!

Optimized version, works on TIO for n=15 (~20 sec)

Actually, this is the beginning of a non-brute-force approach. I hope somebody will work on it and find a complete solution.

First ideas:

• The sum of the output array is the last element (max) of the input array.
• The sum of the output array minus the first (or the last) element, is the second last element of the input array.
• If an array is a solution, then the reverse array is a solution too, so we can assume the first element is the difference between the last 2 elements of the input array.
• The second element can be the difference between second and third or second and fourth last element of the input array.

Which brings us to the next optimization:

Ruby, 175 bytes

->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product([a[-2]-a[-3],a[-2]-a[-4]],*[s=a[0,r]]*(n-2)).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

Try it online!

~8.5 seconds on TIO. Not bad...

...and so on (to be implemented)

Answer 3

Haskell, 117 111 bytes

6 bytes saved thanks to @nimi!

f r i n s|n<1=[r|r==[]]|1<2=[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
n&s=f s[]n s

Try it online!

This computes all solutions. The helper function f builds them incrementally, the r argument contains the values of \$ S \$ that were not yet seen, the i argument contains the sums that include the newest element, n is the remaining number of elements that are needed, and s is always the given set.

When n is zero (golfed to n<1) the list must be ready, so we check if all values have been seen. If not, we return an empty list to indicate no solutions, else we return a singleton list containing an empty list, to which the chosen elements will be prepended. This case could also have been handled with the additional equations

f [] _ 0 _=[[]]
f _ _ 0 _=[]

If n is not zero, we return

[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
 ^1^ ^2^^ ^......3......^ ^.....4.....^ ^.............5.............^

This is the list of (1) lists where the first element (2) comes from s and the rest (5) comes from the recursive call, under the condition (4) that all new sums are in s. The new sums are computed in (3) - note that t is drawn from a singleton list, an ugly golfing hack for what in idiomatic Haskell would be let t=y:map(y+)i. The recursive call (5) gets as new r set the old one without those elements that appear among the new sums t.

The main function & calls the helper function saying that we still have to see all values (r=s) and that there are no sums yet (i=[]).

For seven more bytes, we can restrict the computation to only give the first result (if any), which is much faster and handles all test cases in less than 2 seconds.

Try it online! (this is the first result only variation of the old version)

Answer 4

Clean, 177 bytes

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(?{#u\\u<-s|u<=(last s)-n}(last s)n)
?e s n|n>1=[[h:t]\\h<-:e|h<=s-n,t<- ?e(s-h)(n-1)]=[[s]]

Try it online!

Takes about 40 seconds on my machine for the n=15 test case, but it times out on TIO.

Clean, 297 bytes

import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(~[u\\u<-s|u<=(last s)-n](last s)n(reverse s))
~e s n a|n>4=let u=a!!0-a!!1 in[[u,h:t]\\h<-[a!!1-a!!2,a!!1-a!!3],t<- ?e(s-u-h)(n-2)]= ?e s n
?e s n|n>1=[[h:t]\\h<-e,t<- ?(takeWhile((>=)(s-n-h))e)(s-h)(n-1)]=[[s]]

Try it online!

This one includes some optimisations made by G B as well as some of my own. I think a few of them can be made more generic, so I'll add an explanation once that's done.

It takes about 10 seconds on my machine, 40 seconds on TIO.

Answer 5

Python 3, 177 bytes

from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):
  a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];
  {sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)

Try it online!

(some newlines/spaces added to avoid readers having to scroll the code)

A direct port of my Jelly answer (with some modifications, see "note" section below)

Local run result:

[user202729@archlinux golf]$ printf '%s' "from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];{sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)" > a.py
[user202729@archlinux golf]$ wc -c a.py
177 a.py
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25], 10)' 2>/dev/null
[1, 4, 1, 1, 1, 1, 1, 7, 7, 1]

real    0m3.125s
user    0m3.119s
sys     0m0.004s
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31], 15)' 2>/dev/null
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]

real    11m36.093s
user    11m33.941s
sys     0m0.387s
[user202729@archlinux golf]$ 

---

I heard that itertools is verbose, but my best combinations implementation is even more verbose:

c=lambda s,n,p:s and c(s[1:],n-1,p+s[:1])+c(s[1:],n,p)or[]if n else[p]

---

Note.

• Using division/modulo in a[p//n:p%n+1] takes about 2x longer, but saves some bytes.
• This is a bit different from the Jelly answer -- the Jelly answer iterates backwards.
• Thanks to combinations returning an iterator, this is more memory-friendly.

Answer 6

Jelly, 35 bytes

Ẇ§QṢ⁼³
;³ṫ-¤0;I
ṖṖœcƓ_2¤¹Ṫ©ÇѬƲ¿ṛ®Ç

Try it online!

Run locally: (n=15 takes more than 1 GB of RAM)

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,23,24,25]'<<<10
[8, 6, 2, 1, 1, 1, 1, 3, 1, 1]
real    0m1.177s
user    0m0.000s
sys     0m0.015s

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 2
6, 27, 28, 30, 31]'<<<15
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]
real    12m24.488s
user    0m0.000s
sys     0m0.015s

(actually I ran the UTF8-encoded version, which takes more than 35 bytes, but the result is the same anyway)

This solution uses short-circuit to reduce the run-time.

Without short-circuiting, this code takes roughly \$\binom {|S|-2}{n-2} \times \left( \frac {n^3}6 + n^2\log{n^2} \right)\$ operations, which evaluates to \$\binom {26-2}{15-2} \times \left( \frac {15^3}6 + 15^2\log{15^2} \right) \approx 5.79 \times 10^9\$, however due to the inefficiency of Python and Jelly, it takes forever to complete. Thanks to short-circuiting, it can finish much sooner.

Explanation

We note that the sums of all non-empty prefixes are present in the input, and they are strictly increasing. We can also assume that the largest and second-largest element is a prefix sum.

Therefore, we can consider all ways to choose \$n-2\$ distinct elements from first \$|S|-2\$ elements (there are \$\binom {|S|-2}{n-2}\$ such lists), compute the consecutive differences to recover the elements; then check if it's valid naively (get all \$n^2\$ subarrays, compute the sum, uniquify. Total length of the subarrays is about \$n^3 \over 6\$)

---

Untested (but should have identical performance)

Jelly, 32 bytes

Ṫ©ÑẆ§QṢ⁻³
;³ṫ-¤ŻI
ṖṖœcƓ_2¤¹Ñ¿ṛ®Ç

Try it online!

---

More inefficient version (without short circuit):

Jelly, 27 bytes

Ẇ§QṢ⁼³
ṖṖœcƓ_2¤µ;³ṫ-¤0;I)ÑƇ

Try it online!

For the n=15 test, it takes up to 2GB RAM and does not terminate after ~37 minutes.

---

note: Ẇ§ may be replaced with ÄÐƤẎ. It may be more efficient.

Answer 7

APL(NARS), chars 758, bytes 1516

r←H w;i;k;a;m;j
   r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k

G←{H⍵[⍋⍵]}

r←a d w;i;j;k;b;c
   k←↑⍴w ⋄b←⍬⋄r←0 ⋄j←¯1
A: i←1⋄j+←1⋄→V×⍳(i+j)>k
B: →A×⍳(i+j)>k⋄c←+/w[i..(i+j)]⋄→0×⍳∼c∊a⋄→C×⍳c∊b⋄b←b,c
C: i+←1⋄→B
V: →0×⍳∼a⊆b
   r←1

r←a F w;k;j;b;m;i;q;x;y;c;ii;kk;v;l;l1;i1;v1
   w←w[⍋w]⋄r←a⍴w[1]⋄l←↑⍴w⋄k←w[l]⋄m←8⌊a-2⋄b←¯1+(11 1‼m)⋄j←2⋄i←1⋄x←↑⍴b⋄i1←0⋄v1←⍬
I: i1+←1⋄l1←w[l]-w[l-i1]⋄v1←v1,w[1+l-i1]-w[l-i1]⋄→I×⍳(l1=i1)∧l>i1⋄→B
E: r←,¯1⋄→0
F: i←1⋄q←((1+(a-2)-m)⍴0),(m⍴1),0⋄r+←q
A:   i+←1⋄j+←1⋄→E×⍳j>4000
B:   →F×⍳i>x⋄q←((1+(a-2)-m)⍴0),b[i;],0⋄q+←r⋄v←q[1..(a-1)]⋄→A×⍳0>k-y←+/v
   q[a]←k-y⋄→A×⍳l1<q[a]⋄→A×⍳∼q⊆w⋄→A×⍳∼l1∊q⋄→A×⍳∼v1⊆⍦q⋄c←G q∼⍦v1⋄ii←1⋄kk←↑⍴c⋄→D
C:   →Z×⍳w d v1,ii⊃c⋄ii+←1
D:   →C×⍳ii≤kk
   →A
Z: r←v1,ii⊃c

The function G in G x (with the help of H function) would find all the permutations of x. The function d in x d y find if the y array generate following the exercise array x returning a Boolean value. The function F in x F y would return the array r of length x, such that y d r is true (=1) A little long as implementation, but it is this one that calculate all case in test less time... The last case for n=15 it run 20 second only... i have to say this not find many solutions, return just one solution (at last it seems so) in less time (not explored test for different inputs...) 16+39+42+8+11+11+18+24+24+54+11+12+7+45+79+69+12+38+26+72+79+27+15+6+13(758)

  6 F (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)
5 3 2 2 5 5 
  6 F (2, 4, 6, 8, 10, 12, 16)
4 2 2 2 2 4 
  6 F (1, 2, 3, 4, 6, 7, 8, 10, 14)
4 2 1 1 2 4 
  10 F (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
1 1 3 1 2 3 5 1 3 5 
  15 F (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)
1 2 1 3 3 1 3 3 1 3 3 1 2 1 3 
  ww←(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
  ww≡dx 1 1 3 1 2 3 5 1 3 5 
1