# Reorder for smallest largest prefix sum

Given a multiset of integers, order them such that the largest absolute prefix sum $$\max_i \left| \sum_{k is smallest. Output any solution if multiple exist.

You can assume input is sorted if it helps.

Test cases:

[1,2,3,4,5] => (Any order)
[-5,-4,1,2,3] => [1,2,-4,3,-5] (or other solutions with value 3)
[-8,4] => [4,-8]
[-9, 4, 9, -6] => [4, -9, 9, -6] (suggested by Jonathan Allan)


Shortest code wins.

• This needs a plain English description and a worked example. Commented Jul 18 at 7:54
• Suggested test case [-9, 4, 9, -6] => [4, -9, 9, -6] Commented Jul 18 at 11:37
• I don't know what is unclear about this question. While the current description is terse there is no ambiguity. Commented Jul 18 at 11:45
• I found it very difficult to understand before I looked at some of the answers. I think Shaggy's request for a worked-example is reasonable. Commented Jul 18 at 11:46
• @DominicvanEssen I'm replying to the close vote not Shaggy's comment. Challenge is clear, I don't think it's very well explained. Although I think the nature of the challenge a worked example wouldn't be so helpful. Commented Jul 18 at 16:58

# Vyxal, 6 bytes

Ṗ≬¦ȧG∵


Try it Online!

     ∵ # Smallest
Ṗ      # Permutation
≬---  # By
G  # Largest
ȧ   # Absolute
¦    # Cumulative sum


# Python 3, 93 bytes

lambda a:min(permutations(a),key=lambda a:max(map(abs,accumulate(a))))
from itertools import*


Try it online!

-45 bytes thanks to Jonathan Allan

-3 bytes thanks to no comment

# Python 3.8 (pre-release), 104 bytes

f=lambda a:a and min((f((a:=a[1:]+[x])[:-1])+[x]for x in a),key=lambda a,i=0:max(abs(i:=i+x)for x in a))


Try it online!

Solution without itertools

• Save a bunch importing the permutations function - TIO Commented Jul 18 at 11:55
• @JonathanAllan fair enough Commented Jul 18 at 12:49
• Oh, you got close I see, impressive. Commented Jul 18 at 16:50
• Is there a problem with accumulate? That is, key=lambda a:max(map(abs,accumulate(a))) Commented Jul 18 at 20:15
• @nocomment thanks! itertools and all its children have very lengthy names, so I try to avoid them as much as I can :) Commented Jul 19 at 8:24

# R, 124108 104 bytes

Edit: -13 bytes thanks to Giuseppe.
Edit2: -4 bytes thanks to pajonk

\(x,n=sum(x|1),m=combn(rep(1:n,n),n))x[m[,order(apply(m,2,\(v)max(cumsum(x[v])^2)/all(table(v)<2)))[1]]]


Attempt This Online!

How?

• Get all combinations v of all indices of input x (including re-use of each index, since there isn't an easy base-R command to get permutations).
• Calculate max(abs(cumsum(x[v]))) for each.
• Divide by all(table(v)<2))): this is zero for combinations with re-used indices, giving Inf after division.
• Get the minimum, and select the elements of the input using the corresponding indices.
• Would combn work here? 111 bytes -- I think it should work but it gives different answers than yours and I didn't bother verifying. Commented Jul 18 at 17:01
• -4 bytes using table to check duplicates. Commented Jul 18 at 18:49
• @Giuseppe, pajonk - Great improvements, thanks to both of you! Commented Jul 18 at 20:07

# Factor + math.combinatorics, 55 bytes

[ <permutations> [ cum-sum vabs supremum ] infimum-by ]


Try it online!

• <permutations> [ ... ] infimum-by Get the smallest permutation by function [ ... ]. The angle brackets aren't special; it's just a naming convention signifying that it's a virtual sequence (similar to a lazy list).
• cum-sum cumulative sum
• vabs vectorized absolute value
• supremum largest

# 05AB1E, 8 bytes

œΣηOÄà}н


Try it online or verify all test cases
or verify all possible outputs (by using an additional group-by after the sort).

Explanation:

œ       # Get all permutations of the (implicit) input-list
Σ      # Sort this list of permutation-lists by:
ηO    #  Cumulative sum:
η     #   Get the prefixes
O    #   Sum each prefix together
Ä   #  Take the absolute value of each sum
à  #  Pop and leave the maximum of those
}н     # After the sort by: take the first/smallest
# (which is output implicitly as result)


# Arturo, 58 bytes

$=>[minimum permutate&'p->max map size p=>[abs∑take p&]]  Try it! ### Explanation $=>[]                   ; a function where input is assigned to &
minimum permutate&'p->  ; minimum permutation of input by; current perm is p
max                     ; max value in
map size p=>[]          ; map over current perm's indices, assign to &
abs                     ; absolute value
∑                       ; sum
take p&                 ; current prefix of current permutation


# R, 136 bytes

\(x)(~x)[order(apply(~x,1,\(v)max(abs(cumsum(v)))))[1],]
~=\(v)if(n<-sum(v|1),{X={};for(i in 1:n)X=rbind(X,cbind(v[i],~v[-i]));X},v)


Attempt This Online!

Permutations in base R are a pain. Code for permutations adapted from here.

• Fails for [-9, 4, 9, -6] (minimal max absolute of prefix sums is 5 with [4, -9, 9, -6]). Commented Jul 18 at 11:41
• I think this fails for input of c(1,-2,2,-1)... Commented Jul 18 at 11:43
• Thanks for spotting that Commented Jul 18 at 12:36

# JavaScript (ES6), 99 bytes

Naive method trying all possible permutations.

f=(a,s=M=f,m,...p)=>m>M||a.map((v,i)=>f(a.filter(_=>i--),q=~~s+v,q*q<m?m:q*q,...p,v))+a?o:(M=m,o=p)


Try it online!

### Commented

f = (             // f is a recursive function taking:
a,              //   a[] = input array
s =             //   s = current sum (initially NaN'ish)
M = f,          //   M = minimum of maximums (initially NaN'ish)
m,              //   m = maximum of squared cumulative sums
//       (initially undefined)
...p            //   p[] = current permutation
) =>              //
m > M ||          // abort if m is greater than M
a.map((v, i) =>   // otherwise, for each value v at index i in a[]:
f(              //   do a recursive call:
a.filter(_ => //     pass a[] ...
i--         //       ... without the i-th element
),            //     end of filter()
q = ~~s + v,  //     define q as s + v
q * q < m ?   //     if q² is less than m:
m           //       leave m unchanged
:             //     else:
q * q,      //       set m to q²
...p,         //     append to p[] ...
v             //     ... the new element v
)               //   end of recursive call
) + a             // end of map()
?                 // if we had m > M or a[] is not empty:
o               //   just return o[]
:                 // else:
(M = m, o = p)  //   update M to m and o[] to p[]


# Jelly, 8 bytes

Œ!ÄAṀƊÞḢ


A monadic Link that accepts a list of integers and yields one with the minimal maximum absolute prefix sum.

Try it online! Or see the test-suite.

### How?

Œ!ÄAṀƊÞḢ - Link: list of integers, A
Œ!       - all permutations of A
Þ  - sort by:
Ɗ   -   last three links as a monad:
Ä      -     cumulative sums
A     -     absolute value (vectorises)
Ṁ    -     maximum
Ḣ - head


# Haskell + hgl, 16 bytes

mB(xM av<scp)<pm


Attempt This Online!

## Explanation

• pm get all permutations
• mB minimum by ...
• scp cumulative sums
• xM av maximum absolute value

# Reflection

This is a fairly straight forward solution. I don't see any potential other ways to do this. Nor do I see any ways in which two or more of the components here might be combined to make this shorter.

# Raku, 41 bytes

*.permutations.min:{([\+] @\$_)>>.abs.max}


[\+] is the cumulative sum (+\ in APL). >>. acts like .map{} (in theory, it might be parallelized, but its results are guaranteed to be in order).

Try it online!

# Haskell, 86 bytes

import Data.List
h=maximum.map abs.scanl1(+)
f=minimumBy((.h).compare.h).permutations


Try it online

Equivalent, more readable version:

import Data.List
partialSums = scanl1 (+)
helper = maximum . map abs . partialSums
answer = minimumBy (\left right -> compare (helper left) (helper right)) . permutations

New contributor
MaroonSphinx is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

# Charcoal, 51 bytes

⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻Ｅθνκ⁺κ⟦μ⟧υＦυＵＭι§θκ≔Ｅυ⌈↔ＥιΣ…ι⊕μη⭆¹§υ⌕η⌊η


Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻Ｅθνκ⁺κ⟦μ⟧υ


Generate all of the permutations of the indices of the input. This is taken from my answer to Count N-Rich Permutations of an Integer Sequence. I use the indices because they're unique and it makes it easier to generate the permutations.

ＦυＵＭι§θκ


Map each index to the actual value from the input list.

≔Ｅυ⌈↔ＥιΣ…ι⊕μη


Calculate the maximum prefix sum for each permutation.

⭆¹§υ⌕η⌊η


Output the permutation with the minimum sum.

# Elisp, 341 330 Bytes

Edit: learned the sort function

(defun x (bag)(if (null bag)'(())(mapcan #'(lambda (e)(mapcar #'(lambda (p) (cons e p))(x(cl-remove e bag :count 1))))bag)))(defun z (a)(car (car (sort(cl-loop for e in (x a) collect(let ((i (cons e (apply 'max(cl-loop for o = (reverse e) then (cdr o) while o collect(abs (apply '+ o)))))))i))'(lambda (j k)(< (cdr j) (cdr k))))))


Used permutation method from here https://lists.gnu.org/archive/html/help-gnu-emacs/2009-06/msg00094.html

(defun permutations (bag)
(if (null bag)
'(())
(mapcan #'(lambda (e)
(mapcar #'(lambda (p) (cons e p))
(permutations
(cl-remove e bag :count 1))))
bag)))
(defun smallest-largest-prefix-sum (a)
(car (car (sort
(cl-loop for e in (permutations a) collect
(let ((i (cons e (apply 'max
(cl-loop for o = (reverse e) then (cdr o) while o collect
(abs (apply '+ o))
)
)
)))i))
'(lambda (j k)
(< (cdr j) (cdr k))))
)))


# Setanta, 225193192 191 bytes

Another brute-force solution, but in a language without a permutation builtin.

gniomh(l){s:=eas@mata(999)p:=0gniomh f(v,w,n,m){ma fad@v<fad@l le i idir(0,fad@l){ma aimsigh@v(i)<0{N:=l[i]f(v+[i],w+[N],n+N,uas(dearbh@mata(n+N),m))}}no ma m<s{p=w s=m}}f([],[],0,0)toradh p}


Try on try-setanta.ie

# Uiua + experimentals, 19 bytes

⊡⊢⍏/↥⌵\+⍉.permute⧻.


Try it online at the Uiua pad

permute just got added as an experimental built-in a couple of hours ago so I thought I'd try this challenge with it, and it does quite nicely.

⊡⊢⍏/↥⌵\+⍉.permute⧻.
⊡⊢⍏                  minimum by
/↥                maximum
⌵               absolute
\+             prefix sum
⍉.           of each
permute⧻.  permutation of the input


# J, 3731 30 bytes

0{[:{{y/:>./|+/\|:y}}i.@!@#A.]


Attempt This Online!

i.@!@#A.] NB. get the permutations:
i.        NB. the range to
@!      NB. the factorial of
@#    NB. the length of the argument
A.] NB. select those permutations of the argument

0{[:{{y/:>./|+/\|:y}} NB. reorder for smallest largest prefix sum:
0{[:                  NB. first of
{{y/:       |:y}} NB. sorting those by each's
>./          NB. maximum
|         NB. absolute
+/\      NB. prefix sum