Mengatur ulang satu set angka ke dalam urutan

8

Pertanyaan

Diberikan satu set angka 9 m[],, yang hanya berisi angka 1 hingga 9 dalam urutan acak, tanpa dua angka sama, buat program dalam bahasa apa pun yang mengatur ulang angka menjadi dalam urutan angka (1, 2, 3, dll. dll) dengan hanya beralih dua angka yang bersebelahan (mis. 1, 3, 2 → 1, 2, 3).

Aturan

  • Anda hanya dapat memodifikasi set dengan mengganti dua angka yang bersebelahan
  • Angka akhir (urutan 1 hingga 9) harus tercantum di m[]
  • Anda dapat menggunakan bahasa apa pun yang Anda inginkan
  • Jawaban dengan jumlah byte terkecil menang

Edit:

Kode Anda tidak harus mencetak output, tetapi array yang disusun ulang harus dalam m[].

Meow Mix
sumber
6
Jadi pada dasarnya algoritma Bubble Sort?
Pengoptimal
@Optimizer Benar
Campuran Meow
1
Apakah Anda harus mencetak langkah perantara?
xnor
Bisakah Anda menunjukkan lebih banyak contoh?
Ismael Miguel
7
bisakah kita mengembalikan 1,2,3,4,5,6,7,8,9?
Ewan

Jawaban:

10

CJam, 15 byte

q~A{{a+$~}*]}*p

Bagaimana itu bekerja:

q~                     e# Read the CJam styled input array (For ex. [1 3 4 2 5 6 8 7 9])
  A{        }*         e# Run the loop 10 times. This is enough times for a 10 length
                       e# input array in a bubble sort
    {    }*            e# reduce
     a+$~              e# Rearrange the pair so that they are sorted
           ]           e# After each loop, wrap the numbers back into the array
              p        e# Print the array after the loops are done

Cobalah online di sini

Pengoptimal
sumber
9

Mathematica, 38 byte

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

Ini adalah fungsi yang tidak disebutkan namanya mengambil array, yang menerapkan aturan penggantian sampai pola tidak dapat ditemukan lagi. Pola adalah daftar yang memiliki dua elemen berurutan bdan di cmana b > c, dan aturannya mengatakan untuk menukar bdan ctetapi membiarkan array tidak tersentuh.

Ada banyak gula sintaksis di sini, tetapi kode ini sebenarnya sangat mudah dibaca jika Anda tahu sedikit tentang Mathematica:

# //. {a___,b_,c_,d___} /; b>c :> {a,c,b,d} &
^  ^     ^   ^          ^      ^            ^
|  |     |   |          |      |            |
|  |     |   | Declares an unnamed function |
|  |     |   |          |      |
| The function's argument      |
   |     |   |          |      |
   | Replace while possible... |
         |   |          |      |
         | Zero or more list elements.
             |          |      |
             | A single list element
                        |      |
                        | A condition for the pattern
                               |
                               | What to replace the pattern with
Martin Ender
sumber
9

Python 3, 72 byte

from random import*
while m!=sorted(m):p=randrange(8);m[p:p]=m.pop(p+1),

Pendekatan bogosort (semacam bodoh): menukar elemen tetangga secara acak sampai array akan diurutkan. Biasanya berjalan di bawah satu detik.

2 byte berkat @xnor.

randomra
sumber
4

Python 2, 45

for i in range(8)*8:m[i:i+2]=sorted(m[i:i+2])

Siklus di sekitar daftar, mengurutkan pasangan elemen berurutan. Indeks iberputar hingga 0,1,2,3,4,5,6,7delapan kali, yang menjamin semua elemen menggelembung dan daftar diurutkan.

Tidak
sumber
4

Pyth, 13 - 15 byte

Solusi yang melakukan swapping yang diminta, dan tidak menghasilkan output:

#X=Qhf>FT.:Q2

Solusi yang melakukan swapping yang diminta, dan mencetak status perantara daftar di setiap langkah:

#QX=Qhf>FT.:Q2

Solusi yang melakukan swapping yang diminta, dan mencetak status akhir daftar:

#X=Qhf>FT.:Q2;Q

Demonstrasi solusi tengah di atas.

Metode bertukar nilai yang berdekatan diambil dari jawaban @ Jakube.

Program menggunakan #, pernyataan loop hingga kesalahan, untuk menukar pasangan elemen yang berdekatan yang tidak berurutan hingga tidak ada pasangan yang demikian, pada titik mana h, fungsi kepala, melempar kesalahan, mengakhiri program.

isaacg
sumber
Mengeluarkan hal-hal tambahan yang tidak diminta oleh pertanyaan dianggap sebagai celah standar.
Pengoptimal
@ Opptizer Sebenarnya, OP tidak menyebutkan output sama sekali. Itu hanya berbicara tentang memodifikasi satu set angka. Oleh karena itu, keberatan yang sama dapat dibuat tentang sebagian besar jawaban di sini. Saya akan mencatat ini dalam jawaban saya.
isaacg
Anda seharusnya bertanya pada OP. Saya hanya bertanya. Tapi saya pikir itu sudah diberikan dan Anda hanya menyalahgunakan kesunyian untuk membuat program Anda lebih pendek: P
Optimizer
@ Pengoptimal Memperbarui jawaban saya sesuai dengan itu.
isaacg
1
Saya memilih versi pertama, set diurutkan dan tidak diperlukan output. Sangat berguna untuk menambah keluaran hanya untuk memverifikasi bahwa program bekerja, tetapi itu adalah bagian dari tes dan tidak dihitung.
edc65
3

Retina , 95 93 byte

Tidak terlalu kompetitif (dan mungkin masih golf), tapi di sini kita mulai ...

(.)1
1$1
([^1])2
2$1
([4-9])3
3$1
([5-9])4
4$1
([6-9])5
5$1
([7-9])6
6$1
(8|9)7
7$1
)`98
89
<empty>
<empty>

Di mana <empty>seharusnya ada baris kosong.

Karena semua angka adalah digit tunggal, ini hanya mengharapkan string dengan semua 9 digit sebagai input dan akan dicetak 123456789setelah berhasil mengurutkannya. Setiap tahap melakukan satu swap dan )1`menunjukkan bahwa semua kecuali tahap terakhir harus diulang sampai hasilnya berhenti berubah.

Tahap kosong pada akhirnya diperlukan, karena jika tidak kita akan mendapatkan hasil antara setiap kali 98tahap diproses.

Berikut adalah semua hasil antara (setiap kali itu berubah) untuk menjalankan contoh:

451629387
451269387
451263987
451263978
415263978
412563978
412536978
412536798
412536789
142536789
124536789
124356789
123456789

(Saya memperoleh ini dengan menambahkan :opsi ke setiap tahap, dan menyingkirkan duplikat berturut-turut secara manual.)

Martin Ender
sumber
3

Pyth, 17 byte

uXGhaf>FT.:G2]Z)Q

Berpindah item dalam daftar benar-benar mahal di Pyth. Jadi, inilah solusi yang menyenangkan, yang sedikit meregangkan aturan. Itu mungkin tidak valid.

Cobalah secara online: Pyth Compiler / Executor

Penjelasan

Pertama-tama, kompleksitas waktu kode saya adalah O(n^3). Tapi ini bukan bagian yang menarik. Pertanyaannya tidak mengatakan apa pun tentang kerumitannya.

Bagian penting adalah, bagaimana saya mengganti dua elemen dalam daftar. Katakanlah saya ingin mengganti elemen m[3]dan m[4]. Saya tidak peduli dengan indeks 3dan 4sama sekali. Saya cukup membuat daftar kedua, yang menggantikan setiap elemen sama m[3]dengan angka m[4]dan setiap angka sama m[4]dengan nilai m[3]. Karena daftar tidak mengandung duplikat, ini mensimulasikan beralih dua nilai ini. Jika ada duplikat, seperti pada input [1, 3, 2, 2], hasilnya akan menjadi [1, 2, 3, 3]. Dan jika Anda memberi input [1, 2, 1], itu akan berakhir dalam loop yang tak terbatas. Saya tidak secara eksplisit membuat daftar kedua, itu hanya bagian dari implementasi Pyth tentang metode translate. Jika Anda mencetak daftar saat ini ( lihat di sini), ini memberikan nilai yang benar, yang Anda harapkan.

                   implicit: Q = input list
u               Q  set G = Q, update G as long with the following statements, 
                   until it stops changing: 
         .:G2         all pairs (G[i],G[i+1])
     f>FT             filter for pairs T, where T[0] > T[1]
    a        ]Z       add to this list of pairs [0] 
                      (ensures that the filtered list is always non-empty)
   h                  take the first element
 XG            )      translate G by this pair (switches the values T[0] with T[1])
                   print implicitly at the end 
Jakube
sumber
2

JavaScript (ES6) 56

Fungsi rekursif yang mengatur ulang daftar yang diberikan di tempat.

F=l=>l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l)

Catatan

  • Di JS, untuk nilai numerik apa pun v: v> undefined == false, v <undefined == false. Jadi pergi ke luar batas array tidak menjadi masalah jika kita menggunakan perbandingan yang tepat

  • Ketika array pada akhirnya diurutkan, fungsi di dalam 'some' mengembalikan false dan rekursi berakhir

  • Nilai yang dikembalikan jika swap adalah array 2 elemen, dan nilainya selalu 'benar'. Itu berfungsi bahkan ketika satu atau lebih elemen array bernilai 0

  • Bahkan fungsinya bekerja dengan input numerik apa pun, tidak hanya digit tunggal dan tidak berulang. Tidak menemukan cara untuk mengambil keuntungan dari batasan OP ini.

Uji menggunakan snippet (di Firefox) - versi snippet menampilkan nilai daftar saat ini di setiap langkah.

F=l=>(log('L='+l), l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l))

function log(x) {
   L.innerHTML = L.innerHTML +x+'\n' 
}

function go() {
  l = I.value.split(/\D+/g).map(x=>x|0)
  F(l)
  O.innerHTML = '' + l
}  

go()
Unsorted: <input id=I value="2 8 4 7 5 3 9 1 6"><button onclick="go()">-></button>
<br>Sorted: <span id=O></span>
<br>Operations log:<br>
<pre id=L></pre>

edc65
sumber
1

Javascript ( ES6 ), 66 61 53 byte

Berkat aturan baru, saya dapat mengurangi lebih jauh :)

f=x=>x.map((a,i)=>a<(b=x[--i])&&f(x,x[i]=a,x[i+1]=b))


// Snippet demo: (Firefox only)
f(z=prompt().split(/\D+/).map(x=>+x))
alert(z.join(', '));

Berkomentar

f=x=> // recursive function f
    x.map( // map function to array
        (a, i)=> // a = current value, i = current index
            a < (b = x[--i]) && // poll value of previous index, compare less than
                                // comparison always false at first index as undefined will always be less
                f(x, x[i] = a, x[i + 1] = b) // if true, swap values and call f
    )
nderscore
sumber
0

C, 183

main(c,d,s){int a[10];for(c=0;c<10;c++)scanf("%d", &a[c]);for (c=0;c<10;c++){for(d=0;d<10-c-1;d++){if(a[d]>a[d+1]){s=a[d];a[d]=a[d+1];a[d+1]=s;}}}for(c=0;c<10;c++)printf("%d", a[c]);}

Itu belum golf, selain nama variabel.

Joshpbarron
sumber
0

Haskell, 59 byte

s e(h:t)=min e h:max e h:t
f l=iterate(init.foldr s[9])l!!9

Fungsi smenempatkan elemen edi depan atau di tempat kedua daftar tergantung pada apakah itu kurang atau lebih besar dari elemen pertama daftar. Melipat ske dalam daftar input memungkinkan gelembung elemen terkecil ke depan. Saya melipat ke dalam daftar yang berisi satu 9yang segera saya hapus setelahnya init, sehingga saya tidak perlu memeriksa daftar kosong di s. iteratemengulangi proses pelipatan selamanya untuk membuat daftar hasil antara. Hasil akhir adalah elemen ke-9 dari daftar ini.

nimi
sumber
0

Perl, 68 byte

{for(0..7){if($m[$_]>$m[$_+1]){splice@m,$_,2,$m[$_+1],$m[$_];redo}}}

Kode tidak dikunci

 {                                             # Block runs once unless redo is called

     for (0..7) {                                 # Loop index is in $_

         if ($m[$_] > $m[$_+1]) {                 # Check if swap needed

             splice @m, $_, 2, $m[$_+1], $m[$_];  # Replace a two element slice of
                                                  # the array with those 
                                                  # two elements reversed

             redo                                 # Restart the block over
         }
     }
}
Ralph Marshall
sumber