Definition

Ein Vektor a enthaltend n Elemente werden gesagt, majorize oder dominate eine Vektor b mit n Elementen iff für alle Werte k , so dass 1 ≤ k ≤ n , wobei die Summe des ersten Elements von einer ^↓ durch die k - te Element von einer ^↓ größer ist als oder gleich der Summe der ersten bis k- ten Elemente von b ^↓ , wobei v ^↓ den in absteigender Reihenfolge sortierten Vektor v darstellt .

Das ist,

                          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

Dabei werden a und b in absteigender Reihenfolge sortiert.

Für diese Herausforderung verwenden wir eine leichte Verallgemeinerung der Majorisierung: Wir werden sagen, dass eine Liste eine unsortierte Majorisierung einer anderen ist, wenn alle oben genannten Ungleichungen wahr sind, ohne a und b zu sortieren . (Dies ist natürlich mathematisch nutzlos, macht die Herausforderung jedoch interessanter.)

Herausforderung

Bei einer Eingabe von zwei unterschiedlichen Listen a und b von ganzen Zahlen im Bereich von 0 bis 255 (einschließlich) geben beide Listen der Länge n ≥ 1 aus, ob die erste Liste die zweite unsortiert ( a > b ), die zweite unsortiert Majorisiert die erste ( b > a ) oder keine.

Optional können Sie die Länge der beiden Listen als Eingabe festlegen. Die Ausgabe muss immer einer von drei unterschiedlichen Werten sein, aber die Werte selbst können beliebig sein (bitte geben Sie an, welche Werte für a > b , b > a und keine in Ihrer Antwort stehen).

Testfälle für a > b :

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

Testfälle für b > a :

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

Testfälle ohne Majorisierung:

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

Jelly , 10 8 6 Bytes

2 Bytes dank @orlp.

2 Bytes dank @Dennis.

_+\ṠQS

Probieren Sie es online!

1für a>b, -1für a<b, 0für keine Majorisierung.

_+\ṠQS

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

Wenn beide waren 1und -1vorhanden (einige kumulativen Summen sind größer, manche kleiner), dann wäre der letzte Schritt erzeugen 0.

ngn / apl, 11 Bytes

{+/∪×+\⍺-⍵}

Basierend auf der Methode in der Antwort von @Leaky Nun .

Gegeben seien zwei Listen A und B , finden die Differenz zwischen jedem Wert element, oder lassen C = A - B . Dann finden Sie die kumulativen Summen von C und nehmen Sie das Vorzeichen von jedem. Die Summe der eindeutigen Vorzeichenwerte ist das Ergebnis. Wenn A > B ist , ist das Ergebnis 1, wenn A < B ist das Ergebnis -1, und wenn es keine Mehrheit gibt, ist das Ergebnis 0.

Probieren Sie es online aus.

Julia, 30 Bytes

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

4 Bytes gespart dank @Dennis!

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]]]

Eine anonyme Lambda-Funktion. Gibt zurück, [True,False]ob a>b, [False,True]ob b>aoder [False,False]ob keines davon wahr ist. Ich hoffe das ist okay.

Probieren Sie es 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]

Grundsätzlich eine Portierung meiner Gelee-Antwort .

Die Tatsache, dass der Gültigkeitsbereich innerhalb der Funktion unterbrochen ist und die Variable innerhalb der Funktion nicht definiert werden kann, bedeutet, dass ich dies [xxx].map(i->yyy)[0]anstelle von tun müsste var a=xxx;yyy.

Übernimmt das transponierte Array als Eingabe.

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)

Teste es auf Ideone .

Rubin, 72 59 Bytes

Gibt 1für a>b, -1für a<b, 0für keines von beiden zurück.

-13 Bytes aus dem Summentrick von @Dennis in ihrer Python-Antwort

Probieren Sie es 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

Ausgänge:

• 1 zum a>b
• 2 zum b>a
• 3 für weder

Durchläuft die Liste und verfolgt die laufende Summe tder Unterschiede. Die Zahl gibt an s, welche Zeichen als Zwei-Bit-Zahl angesehen wurden r: Positive im rechten Bit und negative im linken Bit. Dies geschieht über cmp(t,0)%3, was gibt

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

Wenn Sie ordies und den aktuellen Wert von nehmen, werden rdie 2 Bits mit aktualisiert or, wobei Nullwerte keine Wirkung haben.

Javascript (mit externer Bibliothek-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)

Link zu lib: https://github.com/mvegh1/Enumerable

Codeerklärung: Vektor a und b übergeben, globale Funktion z erzeugen. z erstellt zunächst ein Array von Ganzzahlen aus 1 für eine Anzahl von a.length. .All überprüft, ob das Prädikat für jedes Mitglied von a wahr ist. Dieses Prädikat besagt, dass Sie a als eine Aufzählung laden, eine Zählung dieser Aufzählung vornehmen müssen, die dem aktuellen Iterationswert des von uns erstellten Bereichs entspricht, und diese zusammenfassen müssen. Überprüfen Sie, ob das> = dieselbe Logik aus Array "b" ist. Also rufen wir z in der Reihenfolge von (a, b) auf und vergleichen dies mit der Reihenfolge von (b, a) ... wenn gleich, geben wir 0 zurück, um anzuzeigen, dass es keinen Major gibt. Andernfalls geben wir 1 zurück, wenn (a, b) wahr ist, andernfalls -1