pengantar

Misalkan Anda ingin menghitung maksimum ekor dari daftar angka, yaitu, maksimum setiap sufiks nonempty. Salah satu cara untuk melakukannya adalah dengan berulang kali memilih satu nomor dan menggantinya dengan angka yang lebih tinggi setelah itu, sampai ini tidak mungkin lagi. Dalam tantangan ini, tugas Anda adalah melakukan satu langkah dari algoritma ini.

Tugas

Input Anda adalah daftar bilangan bulat L , yang mungkin kosong. Output Anda akan menjadi daftar L di mana tepatnya satu angka L _i telah digantikan oleh L _{j lain} , di mana L _i <L _j dan i <j .

Dengan kata lain, Anda harus mengganti satu nomor dengan angka yang lebih tinggi yang terjadi setelahnya.

Anda dapat memilih i dan j secara bebas di antara semua pasangan yang valid, dan pilihannya bisa tidak deterministik.

Jika i dan j seperti itu tidak ada (yaitu L tidak meningkat), output Anda harus L tidak berubah.

Contoh

Pertimbangkan input L = [3, 1, 4, -1, 2] . Operasi yang mungkin adalah untuk mengganti 3 dengan 4 , ganti 1 dengan 4 , ganti 1 dengan 2 , atau ganti -1 dengan 2 . Jadi output yang mungkin adalah:

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

Jika Anda mengulangi operasi cukup kali, hasil akhirnya akan [4,4,4,2,2] , yang justru merupakan daftar ekor maxima dari L .

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Dalam kasus yang terakhir, Anda dapat memodifikasi input di tempat alih-alih mengembalikan array baru, jika bahasa Anda memungkinkan. Format input dan output fleksibel karena alasan tertentu.

Hitungan byte terendah menang.

Uji kasus

Semua output yang mungkin ditampilkan.

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

Menyimpan satu byte berkat @Neil, terima kasih lagi ke @ user81655

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

Tepat ketika tampaknya reduceRightmungkin akhirnya memiliki kesempatan, .mapmuncul lagi ...

Mathematica, 37 byte

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

Fungsi murni mengambil daftar bilangan real, dan mengembalikan daftar bilangan real. Mencari pasangan pertama dari entri berurutan dalam urutan "salah", dan menggantikan yang pertama dari pasangan itu dengan yang kedua. Perilaku default yang bagus /.berarti mengembalikan input yang tidak diubah jika perlu.

Catatan samping yang mengasyikkan: jika kita ganti b<cdengan !OrderedQ[{c,b}], maka fungsinya bekerja pada string (dan benar-benar tipe data apa pun setelah urutan yang sesuai dijelaskan). Misalnya #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&pada input {"programming", "puzzles", "code", "golf"}pengembalian {"puzzles", "puzzles", "code", "golf"}.

JavaScript (ES6), 43 39 38 byte

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

Keluaran dengan memodifikasi array di tempat. Sunting: Disimpan 4 byte berkat produk @ETH. Disimpan 1 byte berkat @ user81655.

Haskell , 36 byte

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

Cobalah online!

Lihat melalui daftar untuk elemen berturut-turut a,bdengan a<bdan perubahan mereka untuk b,b.

Ditingkatkan dari 37 byte:

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

Jelly , 13 11 byte

ṫJṀ€ż¹ŒpQ-ị

Mengganti yang paling kanan dari semua angka yang mungkin.

Cobalah online!

Bagaimana itu bekerja

ṫ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 byte

tdt0>0whY>d*0h+

Cobalah online!

Saya bukan penggemar berat solusi ini. Tampaknya sangat tidak efisien bagi saya. Terutama bagian whY>d*dan 0h+.

Python 2, 139 134 93 byte

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

Sangat panjang, tetapi ini adalah upaya pertama.

-5 bytes berkat TemporalWolf
-41 (!!) bytes berkat Value Ink

MATL , 13 byte

ttd0>fX>Q)2M(

Cobalah online!

Penjelasan

Dua kondisi berikut ini setara:

1. Ada angka yang memiliki angka lebih tinggi di sebelah kanannya
2. Ada nomor yang memiliki angka lebih tinggi segera di sebelah kanannya

Kode menggunakan kondisi 2, yang lebih sederhana. Itu menghitung kenaikan berturut-turut dan menemukan yang positif terakhir, jika ada. Untuk dua entri yang terlibat, ia menulis nilai entri kedua ke dalam entri pertama.

Trik ini digunakan untuk menangani kasus ketika tidak ada substitusi yang dapat dilakukan. Perhatikan juga bahwa pengindeksan MATL 1berbasis.

Mari kita gunakan input [3,1,4,-1,2]sebagai contoh.

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 byte

Ini didasarkan pada jawaban oleh xnor , yang menyarankan agar saya mempostingnya sendiri.

EDIT: xnor menemukan byte untuk disimpan.

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

Cobalah online!

Pada dasarnya, saya mengamati bahwa percabangan metode xnor selalu berakhir dengan memilih mana dari ekspresi cabang yang terbesar, karena Haskell menggunakan pemesanan leksikografis untuk daftar. (Kasus ketika a==bjuga berfungsi karena f r>=r, yang dapat dibuktikan secara terpisah dengan induksi.)

Letakkan berbeda, kapan saja b:r > a:f r, maka itu b:radalah jawaban yang benar, dan kalau tidak kita bisa kembali ke a:f r.

Jadi, alih-alih memeriksa a<bterlebih dahulu, saya hanya menghitung kedua ekspresi dan mengambil maksimum. Ini bisa memberikan ledakan eksponensial, meskipun kemalasan Haskell menghindari itu kecuali adan bsama.

Python 3, 79 byte

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

Mutasi array asli (daftar) yang diberikan padanya. Saya tidak senang bahwa ini bukan lambda dan saya yakin ada optimisasi yang lebih baik; Semoga saya akan membahasnya nanti.

Penjelasan singkat

Dibutuhkan maks array melewati elemen saat ini (dimulai dengan nol). Kemudian membandingkan ini dengan elemen itu sendiri: jika maks lebih besar, ganti elemen saat ini dengan itu dan berhenti, jika tidak, bertambah satu dan terus mencobanya.

Ruby, 66 61 byte

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

Cobalah online!

C, 47 byte

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

Implementasi rekursif mengambil sebagai inputnya pointer ke elemen pertama array, dan panjang array. Memodifikasi array di tempat.

SWI-Prolog, 70 byte

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

Klausa pertama menggantikan elemen pertama dari daftar dengan nilai maksimum dari sisa daftar, tetapi hanya jika maks ini lebih besar. Klausa kedua secara rekursif menyebut predikat untuk ekor daftar. Jika tidak ada klausa ini yang berhasil, klausa ketiga hanya mengembalikan input.

Ini mengembalikan hanya salah satu solusi yang mungkin. Itu sepele untuk menemukan mereka semua dengan kode yang sangat mirip, tetapi kemudian kasus di mana tidak ada perubahan yang mungkin membutuhkan lebih banyak byte untuk menangani.

Contoh:

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

R, 71 byte

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

C, 80 byte

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;}}

Telepon dengan:

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 byte

Cobalah secara online -1 byte berkat @TemporalWolf
-25 bytes berkat @ValueInk
-7 bytes berkat @Cole

Fungsi yang mengubah array input

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

Jika tidak perlu berhenti setelah iterasi pertama, itu akan sedikit lebih cantik

Python 2, 60 byte

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

Cobalah secara Online!

Penjelasan: Secara rekursif memeriksa apakah elemen yang diberikan kurang dari maxelemen dalam sisa daftar. Jika demikian, kembalikan daftar dengan maxmengganti elemen pertama.

TI-Basic, 72 byte

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

Penjelasan:

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 byte

Bilangan bulat input diteruskan sebagai argumen ke skrip.

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

Kerusakan:

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);

Kerusakan

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 byte

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

Contoh penggunaan: f [1,1,2,1]-> [2,1,2,1]. Cobalah online! .

Jika daftar input memiliki setidaknya satu elemen, ikat bke elemen pertama dan lke seluruh daftar. Jika ltidak kosong dan bkurang dari maksimum l, kembalikan yang maksimum diikuti oleh l, yang lain kembali bdiikuti oleh panggilan rekursif dari f l. Jika daftar input kosong, kembalikan.

Racket 202 byte

(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)

Tidak Disatukan:

(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.

Pengujian:

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

Keluaran:

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

C, 67 byte

Single Run, 67 byte Live

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

Satu Langkah, 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;}}

Tail Maxima, 96 byte 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 byte

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]

Cobalah online!