Menerapkan algoritma pengurutan Thanos

93

Algoritma pengurutan seperti ini:

Sementara daftar tidak diurutkan, ambil setengah dari semua item (hapus item dari daftar). Lanjutkan sampai daftar diurutkan atau hanya satu item yang tersisa (yang diurutkan secara default). Algoritma pengurutan ini dapat memberikan hasil yang berbeda berdasarkan implementasi.

Prosedur penghapusan item tergantung pada implementasi untuk memutuskan, tetapi daftar tersebut harus setengah dari sebelum setelah satu melewati prosedur penghapusan item. Algoritme Anda dapat memutuskan untuk menghapus bagian pertama atau daftar, bagian terakhir dari daftar, semua item ganjil, semua item genap, satu per satu hingga daftar sepanjang setengah, atau apa pun yang tidak disebutkan.

Daftar input dapat berisi jumlah item yang sewenang-wenang (dengan alasan, katakanlah hingga 1000 item), tidak hanya daftar 2 item yang dapat dibagi dengan sempurna. Anda harus menghapus (n + 1) / 2 atau (n-1) / 2 item jika daftar ini ganjil, baik hardcode atau diputuskan secara acak selama runtime. Putuskan sendiri: apa yang akan dilakukan Thanos jika alam semesta mengandung jumlah aneh makhluk hidup?

Daftar ini diurutkan jika tidak ada item yang lebih kecil dari item sebelumnya. Duplikat dapat terjadi pada input, dan dapat terjadi pada output.

Program Anda harus menggunakan array bilangan bulat (via stdin atau sebagai parameter, item individual atau parameter array), dan mengembalikan array yang diurutkan (atau mencetaknya ke stdout).

Contoh:

// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]

// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half

[1, 2, 4, 3, 5] dapat memberikan hasil yang berbeda:

// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]

atau:

// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed

atau:

// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed

atau:

// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
vrwim
sumber
Memiliki test case yang sebenarnya membutuhkan multiple snaps untuk beberapa algoritma snapping yang berbeda akan sangat membantu.
String Tidak Terkait
22
Bukankah kita perlu menyortir dan menghilangkan setengah dari jawaban ...
Sumner18
4
Kasus uji yang disarankan: [9, 1, 1, 1, 1]. Algoritme saya sendiri gagal pada input ini
Conor O'Brien

Jawaban:

19

R , 41 byte

x=scan();while(any(x-sort(x)))x=x[!0:1];x

Cobalah online!

Kirill L.
sumber
3
is.unsortedbukannya any(...)41 byte.
Giuseppe
Metode dasar ini adalah 44 byte sebagai fungsi rekursif, mungkin golf: Coba online!
CriminallyVulgar
18

Python 3 , 38 42 39 byte

q=lambda t:t>sorted(t)and q(t[::2])or t

Cobalah online!

-3 bytes terima kasih kepada @ JoKing dan @Quuxplusone

Sara J
sumber
2
40 byte
Jo King
39 byte berkat pengamatan TFeld bahwa permutasi != sorted(t)harus terjadi > sorted(t).
Quuxplusone
12

Brachylog (v2), 6 byte

≤₁|ḍt↰

Cobalah online!

Ini adalah pengiriman fungsi. Input dari kiri, output ke kanan, seperti biasa. (TIO link menggunakan argumen baris perintah yang secara otomatis membungkus fungsi menjadi program lengkap, sehingga Anda dapat melihatnya beraksi.)

Penjelasan

≤₁|ḍt↰
≤₁       Assert that {the input} is sorted {and output it}
  |      Handler for exceptions (e.g. assertion failures):
   ḍ     Split the list into two halves (as evenly as possible)
    t    Take the last (i.e. second) half
     ↰   Recurse {and output the result of the recursion}

Putaran bonus

≤₁|⊇ᵇlᵍḍhtṛ↰

Cobalah online!

Snap itu dimaksudkan untuk menjadi acak, bukan? Berikut adalah versi program yang memilih elemen yang bertahan secara acak (sambil memastikan bahwa setengahnya bertahan di setiap putaran).

≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁            Assert that {the input} is sorted {and output it}
  |           Handler for exceptions (e.g. assertion failures):
   ⊇ᵇ         Find all subsets of the input (preserving order)
     lᵍ       Group them by length
       ḍht    Find the group with median length:
         t      last element of
        h       first
       ḍ        half (split so that the first half is larger)
          ṛ   Pick a random subset from that group
           ↰  Recurse

Ini akan lebih pendek jika kita dapat menyusun ulang elemen, tetapi mengapa algoritma pengurutan ingin melakukan itu ?

ais523
sumber
12
Satu byte per batu infinity.
djechlin
@djechlin byte tak terhingga adalah mengapa Anda harus menggunakan kepala dan terutama rahang.
The Great Duck
10

Perl 6 , 30 byte

$!={[<=]($_)??$_!!.[^*/2].&$!}

Cobalah online!

Fungsi rekursif yang menghapus paruh kedua daftar sampai daftar diurutkan.

Penjelasan:

$!={                         }    # Assign the function to $!
    [<=]($_)??                    # If the input is sorted
              $_                  # Return the input
                !!                # Else
                  .[^*/2]         # Take the first half of the list (rounding up)
                         .&$!     # And apply the function again
Jo King
sumber
8

Java 10, 106 97 byte

L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}

-9 byte terima kasih kepada @ OlivierGrégoire .

Cobalah online.

n+12

Penjelasan:

L->{               // Method with Integer-list as both parameter and return-type
  for(;;           //  Loop indefinitely:
      L=L.subList(0,L.size()/2)){
                   //    After every iteration: only leave halve the numbers in the list
    int p=1<<31,   //   Previous integer, starting at -2147483648
        f=1;       //   Flag-integer, starting at 1
    for(int i:L)   //   Inner loop over the integer in the list:
      f=p>(p=i)?   //    If `a>b` in a pair of integers `a,b`:
         0         //     Set the flag to 0
        :          //    Else (`a<=b`):
         f;        //     Leave the flag the same
    if(f>0)        //   If the flag is still 1 after the loop:
      return L;}}  //    Return the list as result
Kevin Cruijssen
sumber
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} lebih pendek menggunakan stream, tapi saya belum bisa menemukan cara untuk menghindari java.lang.IllegalStateException: stream has already been operated upon or closedkesalahan setelah mengembalikan aliran
Perwujudan Ketidaktahuan
@EmbodimentofIgnorance ini terjadi karena reduceoperasi terminal yang menutup aliran. Anda tidak akan pernah bisa menelepon reducedua kali pada aliran yang sama. Anda dapat membuat aliran baru.
Olivier Grégoire
1
97 byte
Olivier Grégoire
@ OlivierGrégoire Urutan itu terlihat sangat sederhana sekarang sehingga saya melihatnya .. Kadang-kadang dibutuhkan pandangan dari sudut lain untuk melihat yang jelas orang lain awalnya rindukan kurasa. :) terima kasih!
Kevin Cruijssen
1
Jangan khawatir, itu tidak jelas: saya bekerja untuk sampai di sana. Saya menguji setidaknya 10 versi sebelum menemukan yang satu;)
Olivier Grégoire
8

Bahasa Wolfram (Mathematica) , 30 byte

#//.x_/;Sort@x!=x:>x[[;;;;2]]&

Cobalah online!

@ Doorknob menyimpan 12 byte

J42161217
sumber
1
Alih-alih mengambil babak pertama, Anda bisa menyimpan beberapa byte dengan mengambil setiap elemen lainnya ( x[[;;;;2]]).
Gagang pintu
@ Doorknob ya tentu saja ...
J42161217
pikir mungkin ada penghematan dengan menggunakan OrderedQ, tetapi tidak bisa membuatnya bekerja
Greg Martin
@GregMartin Saya menggunakan OrderedQpendekatan pertama saya (lihat suntingan)
J42161217
7

JavaScript (ES6),  49  48 byte

Disimpan 1 byte berkat @tsh

Menghapus setiap elemen ke-2.

f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a

Cobalah online!

Arnauld
sumber
p++&1->a^=1
tsh
6

Ruby , 37 byte

->r{r=r[0,r.size/2]while r.sort!=r;r}

Cobalah online!

GB
sumber
36 byte secara rekursif
Kirill L.
6

05AB1E , 8 7 byte

[Ð{Q#ιн

-1 byte terima kasih kepada @Emigna .

n-12

Cobalah secara online atau verifikasi beberapa kasus uji lagi (atau verifikasi kasus uji tersebut dengan langkah-demi-langkah untuk setiap iterasi ).

7 byte alternatif oleh @Grimy :

ΔÐ{Ê>äн

Menghapus terakhirn2n-12

Cobalah secara online atau verifikasi beberapa kasus uji lagi (atau verifikasi kasus uji tersebut dengan langkah-demi-langkah untuk setiap iterasi ).

Penjelasan:

[        # Start an infinite loop:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
  {Q     #  Sort a copy, and check if they are equal
    #    #   If it is: Stop the infinite loop (and output the result implicitly)
  ι      #  Uninterweave: halve the list into two parts; first containing all even-indexed
         #  items, second containing all odd-indexed items (0-indexed)
         #   i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
   н     #  And only leave the first part

Δ        # Loop until the result no longer changes:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
       #  Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
    >    #  Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
     ä   #  Split the list in that many parts
      н  #  And only leave the first part
         # (and output the result implicitly after it no longer changes)
Kevin Cruijssen
sumber
3
Anda dapat menggunakan ιalih-alih jika Anda beralih ke strategi elemen lainnya .
Emigna
1
Alternatif 7 menggunakan strategi "hapus setengah terakhir":ΔÐ{Ê>äн
Grimy
@ Grimy Itu pendekatan yang cukup bagus juga. Haruskah saya menambahkannya ke posting saya (tentu saja mengkredit Anda), atau Anda ingin mempostingnya sebagai jawaban yang terpisah?
Kevin Cruijssen
Jangan ragu untuk menambahkannya.
Grimy
6

TI-BASIC (TI-84), 47 42 45 44 byte

-1 byte terima kasih kepada @SolomonUcko!

Ans→L1:Ans→L2:SortA(L1:While max(L1≠Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans

Daftar input ada di Ans.
Keluaran dalam Ansdan dicetak secara implisit.

Penjelasan:

Ans→L1                  ;store the input into two lists
Ans→L2
SortA(L1                ;sort the first list
                        ; two lists are needed because "SortA(" edits the list it sorts
While max(L1≠Ans        ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2  ;remove the latter half of the second list
                        ; removes (n+1)/2 elements if list has an odd length
L2→L1                   ;store the new list into the first list (updates "Ans")
SortA(L1                ;sort the first list
End
Ans                     ;implicitly output the list when the loop ends

Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.

Tau
sumber
Saya pikir Anda dapat mengganti not(min(L1=Ansdengan max(L1≠Ansuntuk menyimpan satu byte.
Solomon Ucko
3

Haskell , 57 55 byte (hanya berkat ASCII)

f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x

Cobalah online!


Kode Asli:

f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x

Cobalah online!


Tidak Disatukan:

f xs | sorted xs = f (halve xs)
     | otherwise = xs

sorted xs = or (zipWith (>) xs (tail xs))

halve xs = take (length xs `div` 2) xs
Sachera
sumber
1
Selamat datang di PPCG!
Rɪᴋᴇʀ
56
ASCII
57 :(
ASCII
55
ASCII
3

Oktaf , 49 byte

l=input('');while(~issorted(l))l=l(1:2:end);end;l

Cobalah online! Ini adalah perjalanan di mana lebih membosankan lebih baik. Perhatikan dua entri yang jauh lebih menarik di bawah ini:

50 byte

function l=q(l)if(~issorted(l))l=q(l(1:2:end));end

Cobalah online! Alih-alih solusi imperatif yang tidak menarik, kita dapat melakukan solusi rekursif, hanya dengan satu byte tambahan.

53 byte

f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())

Cobalah online! Ya. Fungsi anonim rekursif, berkat jawaban brilian @ ceilingcat pada pertanyaan saya . Fungsi anonim yang mengembalikan fungsi anonim rekursif dengan mendefinisikan dirinya dalam daftar argumennya. Saya suka fungsi anonim. Mmmmm

Sanchises
sumber
2

MATL , 11 byte

tv`1L)ttS-a

Cobalah online!

Ini berfungsi dengan menghapus setiap item kedua.

Penjelasan

t      % Take a row vector as input (implicit). Duplicate
v      % Vertically concatenate the two copies of the row vector. When read with
       % linear indexing (down, then across), this effectively repeats each entry
`      % Do...while
  1L)  %   Keep only odd-indexed entries (1-based, linear indexing)
  t    %   Duplicate. This will leave a copy for the next iteration
  tS   %   Duplicate, sort
  -a   %   True if the two arrays differ in any entry
       % End (implicit). A new iteration starts if the top of the stack is true
       % Display (implicit). Prints the array that is left on the stack
Luis Mendo
sumber
2
Patah untuk daftar yang awalnya disortir: [1, 2, 3, 4, 5] harus tetap [1, 2, 3, 4, 5]
Falco
@ Falco Terima kasih! Diperbaiki sekarang
Luis Mendo
2

Japt , 10 byte

eUñ)?U:ßUë

Cobalah

eUñ)?U:ßUë     :Implicit input of array U
e              :Compare equality with
 Uñ            :  U sorted
   )           :End compare
    ?U:        :If true then return U else
       ß       :Run the programme again with input
        Uë     :  Every second element of U
Shaggy
sumber
2

Java (JDK) , 102 byte

n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}

Sudah ada jawaban C #, jadi saya memutuskan untuk mencoba jawaban Java.

Cobalah online!

Perwujudan Ketidaktahuan
sumber
Saatnya mencoba F # :)
aloisdg
2

Crystal , 58 byte

Dengan Array#sort( 58 byte ):

->(a : Array(Int32)){while a!=a.sort;a.pop a.size/2;end;a}

Cobalah online!

Tanpa Array#sort( 101 byte ):

->(a : Array(Int32)){while a.map_with_index{|e,i|e>a.fetch i+1,Int32::MAX}.any?;a.pop a.size/2;end;a}

Cobalah online!

Kinxer
sumber
2

Sekam , 6 5 byte

1 byte disimpan berkat Zgarb

ΩΛ<Ċ2

Cobalah online!

Penjelasan

ΩΛ<Ċ2
Ω         Repeat until
 Λ<         all adjacent pairs are sorted (which means the list is sorted)
   Ċ2         drop every second element from the list
Leo
sumber
Ini 11 byte, bukan 6. ›echo -n" ΩΛ <(← ½ "| wc --bytes 11
Mike Holler
@MikeHoller Seperti banyak bahasa golf lainnya, Husk menggunakan halaman kode khusus, agar dapat mengakses lebih banyak karakter yang berbeda: github.com/barbuz/Husk/wiki/Codepage
Leo
Terima kasih, saya belajar sesuatu hari ini :)
Mike Holler
1
Gunakan Ċ2alih-alih (←½untuk menyimpan byte.
Zgarb
2

Gaia , 9 8 byte

eo₌⟨2%⟩↻

Cobalah online!

Penjelasan:

e		| eval input as a list
       ↻	| until
 o		| the list is sorted
  ₌		| push additional copy
   ⟨2%⟩  	| and take every 2nd element
Giuseppe
sumber
2

Julia 1.0 , 30 byte

-x=x>sort(x) ? -x[1:2:end] : x

Cobalah online!

Mengambil setiap elemen kedua dari array jika tidak diurutkan.

niczky12
sumber
gunakan operator ASCII seperti -untuk 20 byte. juga kita hampir selalu tidak menghitung karakter: | jadi alangkah baiknya jika itu dihapus dari header
ASCII-hanya
Mengubahnya. Terima kasih untuk 2 byte!
niczky12
2

C ++ (gcc) , 103 byte

Saya tidak dapat berkomentar, tetapi saya meningkatkan versi dari movatica dengan mengurangi menyertakan, dan menggunakan otomatis.

-2 Bytes: ceilingcat
-2 Bytes: ASCII-only

#include<regex>
auto f(auto l){while(!std::is_sorted(l.begin(),l.end()))l.resize(l.size()/2);return l;}

Cobalah online!

peterzuger
sumber
1
alasan apa pun yang tidak bisa Anda gunakan l.size()/2?
ASCII-hanya
Ya, itu tidak bekerja seperti itu :)
peterzuger
1
maksud kamu apa? mengembalikan daftar ukuran (n+1)/2atau (n-1)/2keduanya valid. hmm ....
ASCII saja
Ohh oops tidak melihat itu terima kasih
peterzuger
1

VDM-SL , 99 byte

f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 

Tidak pernah dikirimkan dalam vdm sebelumnya, jadi tidak pasti tentang aturan khusus bahasa. Jadi saya telah mengirimkan definisi fungsi yang mengambil a seq of intdan mengembalikan aseq of int

Program lengkap untuk dijalankan mungkin terlihat seperti ini:

functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 
Data Kedaluwarsa
sumber
1

Pyth, 10 byte

.W!SIHhc2Z

Cobalah online di sini . Ini menghapus paruh kedua pada setiap iterasi, membulatkan ke bawah. Untuk mengubahnya untuk menghapus babak pertama, pembulatan ke atas, ubah hke e.

.W!SIHhc2ZQ   Q=eval(input())
              Trailing Q inferred
  !SIH        Condition function - input variable is H
   SIH          Is H invariant under sorting?
  !             Logical not
      hc2Z    Iteration function - input variable is Z
       c2Z      Split Z into 2 halves, breaking ties to the left
      h         Take the first half
.W        Q   With initial value Q, execute iteration function while condition function is true
Sok
sumber
Mengambil setiap elemen lain dari daftar lebih pendek. Ganti hcdengan %. Ini juga memungkinkan Anda menghapus variabel lambda yang tertinggal Zdan membiarkan Pyth mengisinya secara implisit, untuk total 2 byte yang disimpan.
hakr14
1

C ++ (gcc) , 139 137 116 byte

-2 byte byx ke ceilingcat, -21 byte thanx ke PeterZuger

#include<regex>
auto f(std::vector<int>l){while(!std::is_sorted(l.begin(),l.end()))l.resize(-~l.size()/2);return l;}

Ubah ukuran vektor ke setengahnya hingga diurutkan.

Cobalah online!

movatica
sumber
1
Impor harus dimasukkan dalam hitungan byte, jadi Anda harus menambahkan includes
Perwujudan Ketidaktahuan
Terima kasih, saya akan menambahkannya.
movatica
1

K (oK) , 22 20 byte

Larutan:

{(*2 0N#x;x)x~x@<x}/

Cobalah online!

Iterate atas input sampai diurutkan ... jika tidak diurutkan ambil n / 2 item pertama.

{(*2 0N#x;x)x~x@<x}/ / the solution
{                 }/ / lambda that iterates
                <x   / indices that sort x ascending (<)
              x@     / apply (@) these indices back to x
            x~       / matches (~) x? returns 0 or 1
 (       ; )         / 2-item list which we index into
          x          / original input (ie if list was sorted)
       #x            / reshape (#) x
   2 0N              / as 2 rows
  *                  / take the first one      

Suntingan:

  • -2 byte terima kasih kepada ngn
streetster
sumber
1
(.5*#x)#x->*2 0N#x
ngn
Saya dianggap melakukan 2 0Ntetapi menganggap itu akan lebih lama (tanpa pengujian), terima kasih!
streetster
0

Retina , 38 byte

\d+
*
/(_+),(?!\1)/+`,_+(,?)
$1
_+
$.&

Cobalah online! Membawa angka yang dipisahkan koma. Penjelasan:

\d+
*

Konversikan ke unary.

/(_+),(?!\1)/+`

Ulangi saat daftar tidak diurutkan ...

,_+(,?)
$1

... hapus setiap elemen genap.

_+
$.&

Konversikan ke desimal.

Neil
sumber
0

C (gcc) , 66 byte

Hapus bagian kedua dari daftar setiap iterasi ( n/2+1elemen jika panjangnya aneh).

Cobalah online!

Mengambil input sebagai pointer ke awal array intdiikuti oleh panjangnya. Output dengan mengembalikan panjang array yang baru (sortir di tempat).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Versi tidak disatukan:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}
Ketidakseimbangan
sumber
Sarankan ~i+nalih-alihi<n-1
ceilingcat