Given a multiset of integers, order them such that the largest absolute prefix sum $$\max_i \left| \sum_{k<i} a_k \right|$$ 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.
Ṗ≬¦ȧG∵
∵ # Smallest
Ṗ # Permutation
≬--- # By
G # Largest
ȧ # Absolute
¦ # Cumulative sum
lambda a:min(permutations(a),key=lambda a:max(map(abs,accumulate(a))))
from itertools import*
-45 bytes thanks to Jonathan Allan
-3 bytes thanks to no comment
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))
Solution without itertools
accumulate? That is, key=lambda a:max(map(abs,accumulate(a)))
\$\endgroup\$
Commented
Jul 18 at 20:15
itertools and all its children have very lengthy names, so I try to avoid them as much as I can :)
\$\endgroup\$
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]]]
How?
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).max(abs(cumsum(x[v]))) for each.all(table(v)<2))): this is zero for combinations with re-used indices, giving Inf after division.
math.combinatorics, 55 bytes[ <permutations> [ cum-sum vabs supremum ] infimum-by ]
<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 sumvabs vectorized absolute valuesupremum largest
œΣη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)
$=>[minimum permutate&'p->max map size p=>[abs∑take p&]]
$=>[] ; 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
\(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)
Permutations in base R are a pain. Code for permutations adapted from here.
[-9, 4, 9, -6] (minimal max absolute of prefix sums is 5 with [4, -9, 9, -6]).
\$\endgroup\$
Commented
Jul 18 at 11:41
c(1,-2,2,-1)...
\$\endgroup\$
Commented
Jul 18 at 11:43
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)
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[]
Œ!Ä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.
Œ!Ä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
mB(xM av<scp)<pm
pm get all permutationsmB minimum by ...scp cumulative sumsxM av maximum absolute valueThis 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.
*.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).
import Data.List
h=maximum.map abs.scanl1(+)
f=minimumBy((.h).compare.h).permutations
Equivalent, more readable version:
import Data.List
partialSums = scanl1 (+)
helper = maximum . map abs . partialSums
answer = minimumBy (\left right -> compare (helper left) (helper right)) . permutations
⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻Ｅθνκ⁺κ⟦μ⟧υＦυＵＭι§θκ≔Ｅυ⌈↔ＥιΣ…ι⊕μη⭆¹§υ⌕η⌊η
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.
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))))
)))
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}
0{[:{{y/:>./|+/\|:y}}i.@!@#A.]
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
⊡⊢⍏/↥⌵\+⍉.⧅≠⊸⧻
⊡⊢⍏/↥⌵\+⍉.⧅≠⊸⧻
⊡⊢⍏ minimum by
/↥ maximum
⌵ absolute
\+ prefix sum
⍉. of each
⧅≠⊸⧻ permutation of the input
[-9, 4, 9, -6] => [4, -9, 9, -6]\$\endgroup\$