Einführung

Angenommen, Sie möchten die Endmaxima einer Liste von Zahlen berechnen, dh das Maximum jedes nicht leeren Suffixes. Eine Möglichkeit besteht darin, wiederholt eine Nummer auszuwählen und durch eine höhere Nummer zu ersetzen, bis dies nicht mehr möglich ist. In dieser Herausforderung besteht Ihre Aufgabe darin, einen Schritt dieses Algorithmus auszuführen.

Die Aufgabe

Ihre Eingabe ist eine Liste von Ganzzahlen L , die leer sein können. Ihre Ausgabe soll die Liste L sein, in der genau eine Zahl L _i durch eine andere L _{j ersetzt wurde} , wobei L _i <L _j und i <j .

Mit anderen Worten, Sie müssen eine Zahl durch eine höhere Zahl ersetzen, die danach auftritt.

Sie können i und j unter allen gültigen Paaren frei wählen , und die Wahl kann nicht deterministisch sein.

Wenn solche i und j nicht existieren (dh L nicht ansteigend ist), soll Ihre Ausgabe L unverändert sein.

Beispiel

Betrachten Sie die Eingabe L = [3, 1, 4, -1, 2] . Die möglichen Operationen sind 3 durch 4 zu ersetzen, 1 durch 4 zu ersetzen, 1 durch 2 zu ersetzen oder -1 durch 2 zu ersetzen . Somit sind die möglichen Ausgaben:

 [  3 ,   1 ,   4 ,  -1 ,   2 ]
 ------------------------------
 [( 4),   1 ,(  4),  -1 ,   2 ]
 [  3 ,(  4),(  4),  -1 ,   2 ]
 [  3 ,(  2),   4 ,  -1 ,(  2)]
 [  3 ,   1 ,   4 ,(  2),(  2)]

Wenn Sie die Operation genügend oft wiederholen, ist das Endergebnis [4,4,4,2,2] , was genau die Liste der Schwanzmaxima von L ist .

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Im letzteren Fall können Sie die Eingabe ändern, anstatt ein neues Array zurückzugeben, sofern Ihre Sprache dies zulässt. Eingabe- und Ausgabeformate sind innerhalb angemessener Grenzen flexibel.

Die niedrigste Byteanzahl gewinnt.

Testfälle

Alle möglichen Ausgaben werden angezeigt.

[] -> []
[1] -> [1]
[1,2] -> [2,2]
[2,1] -> [2,1]
[4,4,4,4] -> [4,4,4,4]
[-1,-3,-10] -> [-1,-3,-10]
[1,3,10] -> [3,3,10] [10,3,10] [1,10,10]
[1,1,2,1] -> [2,1,2,1] [1,2,2,1]
[998,64,2,-94,-789] -> [998,64,2,-94,-789]
[998,2,64,-94,-789] -> [998,64,64,-94,-789]
[3,1,4,-1,2] -> [4,1,4,-1,2] [3,4,4,-1,2] [3,2,4,-1,2] [3,1,4,2,2]
[-1,4,0,4,7,2,3] -> [4,4,0,4,7,2,3] [0,4,0,4,7,2,3] [-1,4,4,4,7,2,3] [7,4,0,4,7,2,3] [-1,7,0,4,7,2,3] [-1,4,7,4,7,2,3] [-1,4,0,7,7,2,3] [2,4,0,4,7,2,3] [-1,4,2,4,7,2,3] [3,4,0,4,7,2,3] [-1,4,3,4,7,2,3] [-1,4,0,4,7,3,3]
[3542,-12311,7662,1672,6081] -> [7662,-12311,7662,1672,6081] [3542,7662,7662,1672,6081] [3542,1672,7662,1672,6081] [6081,-12311,7662,1672,6081] [3542,6081,7662,1672,6081] [3542,-12311,7662,6081,6081]

JavaScript (ES6), 41 40 39 38 Byte

Ein Byte dank @Neil gespeichert, ein weiteres dank @ user81655

x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0)

Gerade als es so aussieht, als ob reduceRightes endlich eine Chance geben könnte, .maptaucht es wieder auf ...

Mathematica, 37 Bytes

#/.{a___,b_,c_,d___}/;b<c:>{a,c,c,d}&

Reine Funktion, die eine Liste reeller Zahlen aufnimmt und eine Liste reeller Zahlen zurückgibt. Sucht nach dem ersten Paar aufeinanderfolgender Einträge in der "falschen" Reihenfolge und ersetzt das erste Paar durch das zweite. Nettes Standardverhalten von /.bedeutet, dass die Eingabe bei Bedarf unverändert zurückgegeben wird.

Amüsante Randnotiz: Wenn wir ersetzen b<cmit !OrderedQ[{c,b}], dann wird die Funktion auf Strings funktioniert (und wirklich jeden Datentyp , sobald die entsprechende Bestellung wird beschrieben). Zum Beispiel #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&bei der {"programming", "puzzles", "code", "golf"}Rückgabe von Eingaben {"puzzles", "puzzles", "code", "golf"}.

JavaScript (ES6), 43 39 38 Byte

a=>a[a.some(e=>e<a[++i],i=0)*i-1]=a[i]

Ausgabe durch Ändern des Arrays an Ort und Stelle. Bearbeiten: 4 Bytes dank @ETHproductions gespeichert. 1 Byte dank @ user81655 gespeichert.

Haskell , 36 Bytes

f(a:r@(b:_))|a<b=b:r|1>0=a:f r
f e=e

Probieren Sie es online!

Durchsuchen Sie die Liste nach aufeinanderfolgenden Elementen a,bmit a<bund ändern Sie sie in b,b.

Verbessert von 37 Bytes:

f(a:b:t)|a<b=b:b:t
f(a:t)=a:f t
f e=e

Jelly , 13 11 Bytes

ṫJṀ€ż¹ŒpQ-ị

Ersetzt die am weitesten rechts stehende aller möglichen Zahlen.

Probieren Sie es online!

Wie es funktioniert

ṫJṀ€ż¹ŒpQ-ị  Main link. Argument: A (array)

 J           Yield all indices of A, i.e., the array [1, ..., len(A)].
ṫ            Dyadic tail; for index k, take all elements starting with the k-th.
             This constructs the array of suffixes.
  Ṁ€         Maximum each; map the monadic maximum atom over the suffixes.
     ¹       Identity; yield A.
    ż        Zip; construct all pairs of elements of the result to the left and the
             corresponding elements of the result to the right.
      Œp     Cartesian product. Construct all arrays that, for each index, take
             either the left or the right element.
        Q    Unique; deduplicate the resulting arrays.
         -ị  At-index -1; select the second to last result.
             The last result is A itself, the first maxima of suffixes.

MATL , 15 Bytes

tdt0>0whY>d*0h+

Probieren Sie es online!

Ich bin kein großer Fan dieser Lösung. Es scheint mir schrecklich ineffizient. Besonders die whY>d*und 0h+Abschnitte.

Python 2, 139 134 93 Bytes

a=input()
for i in range(len(a)):
 for j in a[i+1:]:
    if a[i]<j:a[i]=j;print a;exit()
print a

Schrecklich lang, aber es ist ein erster Versuch.

-5 Bytes dank TemporalWolf
-41 (!!) Bytes dank Value Ink

MATL , 13 Bytes

ttd0>fX>Q)2M(

Probieren Sie es online!

Erläuterung

Die folgenden zwei Bedingungen sind äquivalent:

1. Es gibt eine Zahl mit einer höheren Zahl rechts davon
2. Es gibt eine Zahl, die unmittelbar rechts von sich eine höhere Zahl hat

Der Code verwendet die Bedingung 2, die einfacher ist. Es berechnet aufeinanderfolgende Inkremente und findet das letzte positive, falls vorhanden. Für die beiden beteiligten Einträge schreibt es den Wert des zweiten Eintrags in den ersten.

Dieser Trick wird verwendet, um den Fall zu behandeln, dass keine Substitution durchgeführt werden kann. Beachten Sie auch, dass die MATL-Indizierung 1-basiert ist.

Verwenden wir [3,1,4,-1,2]als Beispiel die Eingabe .

tt    % Get input implicitly and duplicate it twice
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [3,1,4,-1,2]
d     % Consecutive differences
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [-2  3 -5  3]
0>    % Are they positive?
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [0 1 0 1]
f     % Find indices of all positive differences. Result may be empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [2 4]
X>    % Maximum index with a positive difference. Empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 4
Q     % Add 1. Since the addition is elementwise, empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 5
)     % Get the entry of the input at that position
      % STACK: [3,1,4,-1,2], 2
2M    % Push maximum index with a positive difference, again
      % STACK: [3,1,4,-1,2], 2, 4
(     % Assign to that position. Implicitly display
      % STACK: [3,1,4,2,2]

Haskell , 34 33 Bytes

Dies basiert auf der Antwort von xnor , der mir vorschlug, sie selbst zu posten.

BEARBEITEN: xnor hat ein zu speicherndes Byte gefunden.

f(a:r@(b:_))=max(b:r)$a:f r
f e=e

Probieren Sie es online!

Grundsätzlich habe ich festgestellt, dass die Verzweigung der Methode von xnor immer dazu führt, dass derjenige der Verzweigungsausdrücke ausgewählt wird, der am größten ist, da Haskell die lexikografische Reihenfolge für Listen verwendet. (Der Fall a==bfunktioniert dann auch weil f r>=r, was durch Induktion separat nachgewiesen werden kann.)

Anders gesagt , wann immer b:r > a:f r, dann b:rist eine richtige Antwort, und ansonsten können wir darauf zurückgreifen a:f r.

Anstatt also a<bim Voraus zu prüfen , berechne ich einfach beide Ausdrücke und nehme das Maximum. Dies könnte zu einer exponentiellen Explosion führen, obwohl Haskells Faulheit dies vermeidet, es sei denn aund bsind gleich.

Python 3, 79 Bytes

def f(x):
 for i,a in enumerate(x):
  m=max(x[i+1:])
  if m>a:x[i]=m;break

Mutiert das ursprüngliche Array (Liste), das ihm zugewiesen wurde. Ich bin unglücklich, dass dies kein Lambda ist, und ich bin mir sicher, dass es bessere Optimierungen gibt. Ich werde hoffentlich später darauf eingehen.

Kurze Erklärung

Es dauert das Maximum des Arrays nach dem aktuellen Element (beginnend mit der Null). Es vergleicht dies dann mit dem Element selbst: Wenn der Maximalwert größer ist, ersetzen Sie das aktuelle Element durch das Element und stoppen Sie, andernfalls erhöhen Sie den Wert um eins, und versuchen Sie es erneut.

Ruby, 66 61 Bytes

->a{i=r=-1;a.map{|e|m=a[i+=1,a.size].max;r&&m>e ?(r=!r;m):e}}

Probieren Sie es online!

C 47 Bytes

f(p,n)int*p;{n>1?*p<p[1]?*p=p[1]:f(p+1,n-1):0;}

Rekursive Implementierung, die einen Zeiger auf das erste Element eines Arrays und die Länge des Arrays als Eingabe verwendet. Ändert das Array an Ort und Stelle.

SWI-Prolog, 70 Bytes

f([H|T],[S|T]):-max_list(T,S),S>H,!.
f([H|T],[H|R]):-f(T,R),!.
f(I,I).

Die erste Klausel ersetzt das erste Element der Liste durch den Maximalwert des restlichen Teils der Liste, jedoch nur, wenn dieser Maximalwert größer ist. Die zweite Klausel ruft rekursiv das Prädikat für das Ende der Liste auf. Wenn keine dieser Klauseln erfolgreich ist, gibt die dritte Klausel einfach die Eingabe zurück.

Dies ist nur eine der möglichen Lösungen. Es ist trivial, sie alle mit sehr ähnlichem Code zu finden, aber in dem Fall, in dem keine Änderung möglich ist, sind viel mehr Bytes erforderlich.

Beispiel:

?- f([-1,4,0,4,7,2,3], O).
O = [7, 4, 0, 4, 7, 2, 3]

R, 71 Bytes

a=scan()
l=length(a) 
lapply(1:l,function(x){
  a[x]=max(a[x:l])
  a
})

C 80 Bytes

i,j;f(l,n)int*l;{for(i=0;i<n;++i)for(j=i;++j<n;)if(l[i]<l[j]){l[i]=l[j];j=i=n;}}

Rufen Sie an mit:

int main()
{
    int a[5]={3,1,4,-1,2};
    f(a,5);
    for(int k=0;k<5;++k)
        printf("%d ", a[k]);
}

Python 2, 89 Bytes

Probieren Sie es online aus -1 Byte dank @TemporalWolf
-25 Byte dank @ValueInk
-7 Byte dank @Cole

Funktion, die das Eingabearray mutiert

def F(A):
 for i in range(len(A)):
    r=[y for y in A[i+1:]if y>A[i]]
    if r:A[i]=r[0];break

Wenn es nicht nötig wäre, nach der ersten Iteration anzuhalten, wäre es etwas hübscher

Python 2, 60 Bytes

f=lambda x:x and[x[:1]+f(x[1:]),[max(x)]+x[1:]][x[0]<max(x)]

Probieren Sie es online!

Erläuterung: Überprüft rekursiv, ob ein bestimmtes Element kleiner als das maxElement in der restlichen Liste ist. In diesem Fall wird die Liste mit dem maxErsetzen des ersten Elements zurückgegeben.

TI-Basic, 72 Bytes

Prompt L1
If 2≤dim(L1
Then
For(A,1,dim(L1)-1
For(B,A,dim(L1
If L1(A)<L1(B
Then
L1(B→L1(A
Goto E
End
End
End
End
Lbl E
L1

Erläuterung:

Prompt L1          # 4 bytes, input list
If 2≤dim(L1        # 7 bytes, if the list has 2 or 1 element(s), skip this part and return it
Then               # 2 bytes
For(A,1,dim(L1)-1  # 12 bytes, for each element in the list other than the last
For(B,A,dim(L1     # 9 bytes, for each element after that one
If L1(A)<L1(B      # 12 bytes, if the second is larger than the first
Then               # 2 bytes
L1(B→L1(A          # 10 bytes, replace the first with the second
Goto E             # 3 bytes, and exit
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
Lbl E              # 3 bytes
L1                 # 2 bytes, implicitly return L1

sh, 118 Bytes

Ganzzahlen werden als Argumente an das Skript übergeben.

l=("$@");for i in "$@";{ for j in "$@";{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};shift;x=`expr $x+1`;};echo ${l[@]}

Nervenzusammenbruch:

l=("$@");                      #copy original list
for i in "$@";{ for j in "$@"; #check all elements j that follow element i in list
{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};   #if i<j, make i=j; print list, done
shift;                         #makes sure that i is compared only to j that occur after it
x=`expr $x+1`;};               #keeps track of i'th position in the list
echo ${l[@]}                   #prints list if it was unchanged

PHP, 88 Bytes

<?for(;$i+1<$c=count($a=$_GET)&&$a[+$i]>=$a[++$i];);$i>=$c?:$a[$i-1]=$a[$i];print_r($a);

Nervenzusammenbruch

for(;
$i+1<($c=count($a=$_GET))  # first condition end loop if the item before the last is reach 
&&$a[+$i]>=$a[++$i] # second condition end loop if item is greater then before 
;);
$i>=$c?:$a[$i-1]=$a[$i]; # replace if a greater item is found
print_r($a); #Output

Haskell, 48 Bytes

f(b:l)|l>[],m<-maximum l,b<m=m:l|1<2=b:f l
f x=x

Anwendungsbeispiel: f [1,1,2,1]-> [2,1,2,1]. Probieren Sie es online! .

Wenn die Eingabeliste mindestens ein Element enthält, binden Sie es ban das erste Element und lan den Rest der Liste. Wenn lnicht leer und bkleiner als das Maximum von l, geben Sie das Maximum gefolgt von zurück l, andernfalls geben Sie bgefolgt von einem rekursiven Aufruf von zurück f l. Wenn die Eingabeliste leer ist, geben Sie sie zurück.

Schläger 202 Bytes

(let((g(λ(L i n)(for/list((c(in-naturals))(l L))(if(= c i)n l))))(ol'()))
(for((c(in-naturals))(i L))(for((d(in-range c(length L)))#:when(>(list-ref L d)i))
(set! ol(cons(g L c(list-ref L d))ol))))ol)

Ungolfed:

(define (f L)
  (let ((replace (λ (L i n)   ; sub-function to replace i-th item in list L with n;
                   (for/list ((c (in-naturals))
                              (l L))
                     (if (= c i) n l))))
        (ol '()))             ; outlist initially empty; 
    (for ((c (in-naturals))               ; for each item in list
          (i L))
      (for ((d (in-range c (length L)))   ; check each subsequent item in list
            #:when (> (list-ref L d) i))  ; if greater, replace it in list
        (set! ol (cons (replace L c (list-ref L d)) ol)))) ; and add to outlist.
    ol))          ; return outlist.

Testen:

(f '(3 1 4 -1 2))

Ausgabe:

'((3 1 4 2 2) (3 2 4 -1 2) (3 4 4 -1 2) (4 1 4 -1 2))

C 67 Bytes

Single Run, 67 Bytes Live

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)l[j]=fmax(l[i],l[j]);}

Einzelschritt, 78 Byte Live

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)if(l[j]<l[i]){l[j]=l[i];return;}}

Schwanz Maxima, 96 Bytes Live

x;i;j;f(l,n)int*l;{do{x=0;for(i=0;i<n;i++)for(j=0;j<i;j++)if(l[j]<l[i])l[j]=l[i],x=1;}while(x);}

Python 3 , 103 102 Bytes

lambda a:([a[:i]+[max(a[i:])]+a[i+1:]for i in range(len(a))if-~i==len(a)or max(a[i+1:])>a[i]]+[[]])[0]

Probieren Sie es online!