# Unsorted majorization of two lists

### Definition

A vector a containing n elements is said to majorize or dominate a vector b with n elements iff for all values k such that 1 ≤ kn, the sum of the first element of a through the kth element of a is greater than or equal to the sum of the first through kth elements of b, where v represents the vector v sorted in descending order.

That is,

                          a_1 >= b_1
a_1 + a_2 >= b_1 + b_2
a_1 + a_2 + a_3 >= b_1 + b_2 + b_3
...
a_1 + a_2 + ... + a_n-1 >= b_1 + b_2 + ... + b_n-1
a_1 + a_2 + ... + a_n-1 + a_n >= b_1 + b_2 + ... + b_n-1 + b_n


where a and b are sorted in descending order.

For the purpose of this challenge, we will be using a slight generalization of majorization: we will say a list is an unsorted majorization of another if all of the above inequalities are true without sorting a and b. (This is, of course, mathematically useless, but makes the challenge more interesting.)

### Challenge

Given an input of two distinct lists a and b of integers in the range 0 through 255 (inclusive), both lists of length n ≥ 1, output whether the first list unsorted-majorizes the second (a > b), the second unsorted-majorizes the first (b > a), or neither.

You may optionally require the length of the two lists to be provided as input. The output must always be one of three distinct values, but the values themselves may be whatever you want (please specify which values represent a > b, b > a, and neither in your answer).

Test cases for a > b:

[255] [254]
[3,2,1] [3,1,2]
[6,1,5,2,7] [2,5,4,3,7]


Test cases for b > a:

[9,1] [10,0]
[6,5,4] [7,6,5]
[0,1,1,2,1,2] [0,1,2,1,2,1]


Test cases for no majorization:

[200,100] [150,250]
[3,1,4] [2,3,3]
[9,9,9,9,9,0] [8,8,8,8,8,9]

• Can we take a 2-column array as input? Commented Aug 3, 2016 at 20:35
• @LuisMendo Yes, the input may be in any format that does not encode extra information. Commented Aug 3, 2016 at 20:39
• Would an array of pairs be acceptable? Commented Aug 4, 2016 at 4:09

# Jelly, 108 6 bytes

2 bytes thanks to @orlp.

2 bytes thanks to @Dennis.

_+\ṠQS


Try it online!

1 for a>b, -1 for a<b, 0 for no majorization.

_+\ṠQS

_       Difference (vectorized)
+\     Cumulative sum.
Ṡ    Sign of every difference
Q   Deduplicate
S  Sum


If there were both 1 and -1 present (some cumulative sums are bigger, some smaller), then the last step would produce 0.

# ngn/apl, 11 bytes

{+/∪×+\⍺-⍵}


Based on the method in @Leaky Nun's answer.

Given two lists A and B, find the difference between each value elementwise, or let C = A - B. Then, find the cumulative sums of C and take the sign of each. The sum of the unique sign values will be the result. If A > B, the result is 1, if A < B the result is -1, and if there is no majority the result is 0.

Try it online.

# Julia, 30 bytes

a^b=sum(sign(cumsum(a-b))∪0)


Saved 4 bytes thanks to @Dennis!

• In which version of Julia did you test this? Commented Aug 4, 2016 at 2:54
• Oops :P I think this should work. Commented Aug 4, 2016 at 3:25
• Indeed. a^b=sum(sign(cumsum(a-b))∪0) saves a few bytes. Commented Aug 4, 2016 at 3:28

# Python 3.5, 85 bytes:

lambda*e:[all(sum(g[:k])>=sum(h[:k])for k in range(1,-~len(h)))for g,h in[e,e[::-1]]]


An anonymous lambda function. Returns [True,False] if a>b, [False,True] if b>a, or [False,False] if neither of those are true. I hope this is okay.

Try It Online! (Ideone)

# Cheddar, 118 114 bytes

n->[n.map(i->i[0]-i[1]).map((j,k,l)->l.slice(0,k+1).sum).map(i->i>0?1:i<0?-1:0)].map(j->j has 1?j has-1?0:1:-1)[0]


Basically a port of my Jelly answer.

The fact that scope inside function is broken causing inability to define variable inside function means that I would need to do [xxx].map(i->yyy)[0] instead of var a=xxx;yyy.

Takes transposed array as input.

n->[n
.map(i->i[0]-i[1])                     Difference (vectorized)
.map((j,k,l)->l.slice(0,k+1).sum)      Cumulative sum.
.map(i->i>0?1:i<0?-1:0)]               Sign of every difference
.map(j->j has 1?j has-1?0:1:-1)[0]     Deduplicate and Sum


# Python 2, 73 bytes

a,=b,=r={0}
for x,y in zip(*input()):a+=x;b+=y;r|={cmp(a,b)}
print sum(r)


Test it on Ideone.

# Ruby, 72 59 bytes

Returns 1 for a>b, -1 for a<b, 0 for neither.

-13 bytes from cribbing the sum trick off of @Dennis in their Python answer

Try it online!

->a,b{x=y=0;a.zip(b).map{|i,j|(x+=i)<=>y+=j}.uniq.inject:+}


## Python 2, 59 bytes

t=r=0
for x,y in zip(*input()):t+=x-y;r|=cmp(t,0)%3
print r


Outputs:

• 1 for a>b
• 2 for b>a
• 3 for neither

Iterates through the list, tracking the running sum t of differences. The number s tracks what signs have been seen as a two-bit number r: positives in the right bit and negatives in the left bit. This happens via cmp(t,0)%3, which gives

• t>0+1 → 1
• t==00 → 0
• t<0-1 → 2

Taking the or of this and the current value of r updates the 2 bits with or, with zero values having no effect.

# Javascript (using external library-Enumerable) (123 bytes)

(a,b)=>(z=(c,d)=>_.Range(1,c.length).All(x=>_.From(c).Take(x).Sum()>=_.From(d).Take(x).Sum()))(a,b)==z(b,a)?0:(z(a,b)?1:-1)