Golf Acak Hari Ini # 1: Acak Array

35

Tentang Seri

Saya akan menjalankan serangkaian tantangan kode-golf berputar di sekitar tema keacakan. Ini pada dasarnya akan menjadi Lapangan Golf 9-Lubang , tetapi tersebar di beberapa pertanyaan. Anda dapat berpartisipasi dalam setiap tantangan secara individual seolah-olah itu adalah pertanyaan normal.

Namun, saya akan mempertahankan papan peringkat di semua tantangan. Serial ini akan membahas lebih dari 9 tantangan (untuk saat ini), satu diposting setiap beberapa hari. Setiap pengguna yang berpartisipasi dalam 9 tantangan memenuhi syarat untuk memenangkan seluruh seri. Skor keseluruhan mereka adalah jumlah dari kiriman terpendek mereka pada setiap tantangan (jadi jika Anda menjawab tantangan dua kali, hanya jawaban yang lebih baik yang dihitung untuk skor tersebut). Jika ada yang memegang posisi teratas di papan peringkat keseluruhan ini selama 28 hari, saya akan memberi mereka hadiah 500 rep .

Meskipun saya memiliki banyak ide untuk seri ini, tantangan di masa depan belum ditetapkan. Jika Anda memiliki saran, beri tahu saya di pos kotak pasir yang relevan .

Lubang 1: Kocok Array

Tugas pertama cukup sederhana: diberi array integer yang tidak kosong, kocok secara acak. Ada beberapa aturan:

  • Setiap permutasi yang mungkin harus dikembalikan dengan probabilitas yang sama (sehingga shuffle harus memiliki distribusi yang seragam). Anda dapat memeriksa apakah algoritme Anda seragam / tidak memihak dengan mengimplementasikannya dalam JavaScript pada Will it Shuffle , yang akan menghasilkan matriks bias - hasilnya akan terlihat sama seragamnya dengan Fisher-Yates bawaannya atau urutkan (urutan acak) .
  • Anda tidak boleh menggunakan metode bawaan atau pihak ketiga untuk mengocok array atau menghasilkan permutasi acak (atau menghitung semua permutasi). Secara khusus, satu-satunya fungsi acak bawaan yang dapat Anda gunakan adalah mendapatkan satu nomor acak sekaligus . Anda dapat mengasumsikan bahwa setiap metode bilangan acak bawaan berjalan di O (1) dan sangat seragam selama interval yang diminta (dalam pengertian matematika - Anda dapat mengabaikan detail representasi titik mengambang di sini). Jika bahasa Anda memungkinkan Anda memperoleh daftar angka acak m sekaligus, Anda dapat menggunakan fasilitas ini, asalkan angka-angka m independen satu sama lain, dan Anda menghitungnya sebagai O (m).
  • Implementasi Anda tidak boleh melebihi kompleksitas waktu O (N) , di mana N adalah ukuran array yang akan dikocok. Misalnya, Anda tidak dapat "mengurutkan berdasarkan angka acak".
  • Anda dapat mengocok array di tempat, atau membuat array baru (dalam hal ini array lama dapat diubah sesuka Anda).

Anda dapat menulis program atau fungsi lengkap dan mengambil input melalui STDIN, argumen baris perintah, argumen fungsi atau prompt dan menghasilkan output melalui nilai balik atau dengan mencetak ke STDOUT (atau alternatif terdekat). Jika Anda menulis fungsi yang mengocok array di tempatnya, Anda tidak perlu mengembalikannya tentu saja (asalkan bahasa Anda memungkinkan Anda mengakses array yang diubah setelah fungsi kembali).

Input dan output mungkin dalam format string atau daftar yang mudah digunakan, tetapi harus mendukung bilangan bulat sewenang-wenang dalam rentang -2 31 ≤ x <2 31 . Pada prinsipnya, kode Anda harus bekerja untuk array hingga panjang 2 31 , meskipun ini tidak harus sesuai dengan memori Anda atau selesai dalam jumlah waktu yang wajar. (Saya hanya tidak ingin melihat batas ukuran sewenang-wenang untuk loop hardcode atau sesuatu.)

Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.

Papan peringkat

Cuplikan berikut akan menghasilkan papan peringkat di semua tantangan seri.

Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)

Martin Ender
sumber
7
Saya kecewa bahwa kami tidak boleh "pintar" dan menggunakan fungsi perpustakaan selain "mendapatkan nomor acak" . Apakah kita ingin melihat 69 implementasi pengocokan Fisher-Yates? Harap pertimbangkan untuk menghapus aturan ini dalam tugas di masa mendatang. Juga, mengapa batasan kompleksitas waktu? Silakan pertimbangkan untuk bersantai setidaknya O (n ^ 2); Saya juga berpikir seseorang mungkin menemukan implementasi golf terutama jika Anda mengizinkan O (n!).
anatolyg
7
@anatolyg Menghapus jumlah pembatasan untuk setiap jawaban menjadi salah satu sortby(random)(alasan untuk pembatasan waktu) atau hanya .shuffle()(alasan untuk pembatasan bawaan), yang saya pikir jauh lebih pintar daripada harus menerapkan Fisher-Yates atau yang lainnya pendekatan.
Martin Ender
1
Jika mengocok di tempat, apakah suatu fungsi harus mengembalikan array, atau cukupkah itu dimodifikasi? Bisakah saya menulis fungsi shuffle(array)bukan newArray=shuffle(array)?
Geobits
1
@ Bakuriu Mengklaim bahwa Anda dapat mengurutkan dalam waktu linier jika angka-angkanya sedikit mirip dengan mengklaim Anda dapat melakukan apa saja di O (1) jika ukuran inputnya tetap. Juga batasan yang relevan adalah array ukuran tetap, bukan bilangan bulat ukuran tetap - karena ukuran array menentukan seberapa besar Anda memerlukan angka acak Anda. Bagaimanapun, batasan kompleksitas waktu tentu saja untuk algoritma umum yang Anda terapkan, sedangkan batasan ukuran input sudah ada sehingga Anda tidak harus menggunakan bilangan bulat presisi arbitrer jika bahasa Anda tidak menggunakannya di luar kotak .
Martin Ender
2
Mengapa solusi Adm muncul sebagai 43319 byte padahal sebenarnya 14?
boboquack

Jawaban:

20

Dyalog APL, 25 24 byte

Pertama untuk solusi 25 karakter: i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕

                      a←⎕ ⍝ evaluated input, assign to "a"
                     ⍴a   ⍝ length
                    ⍳⍴a   ⍝ 1 2 .. length
                   ⌽⍳⍴a   ⍝ length .. 2 1
                 i←       ⍝ assign to "i"
                ?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
   a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
        ←                 ⍝ in Dyalog, assignment returns its right-hand side
  ⊃                       ⍝ first element, i.e. a[⍵]
                          ⍝ the result from {} is an array of all those a[⍵]

Setelah beberapa transformasi kesetaraan di atas:

i {}¨ ?i  ←→  i {}¨∘? i   ⍝ because A f∘g B ←→ A f g B
          ←→  {}¨∘?⍨ i    ⍝ because f⍨ B ←→ B f B

kita dapat menyingkirkan tugas i←dan menyimpan karakter:

{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕

ngn
sumber
3
... pikiran. sesak nafas.
danwyand
1
bahasa yang harus saya baca kanan ke kiri ?? Wow!
Luminous
5
@ Luminous seperti yang sering terjadi dengan notasi matematika: sin cos ln sqrt x
ngn
4
@ ngn ketika Anda mengatakannya seperti itu yang membuat komentar saya sebelumnya terlihat menggelikan. Ha.
Luminous
5
@ronalchn Ada penyandian 8-bit untuk APL, seperti ini atau yang ini ; Saya mendengar Dyalog menggunakan salah satunya, sebagai alternatif untuk Unicode.
anatolyg
12

80386 kode mesin, 44 24 byte

Hexdump kode:

60 8b fa 0f c7 f0 33 d2 f7 f1 49 8b 04 8f 87 04
97 89 04 8f 75 ed 61 c3

Terima kasih kepada FUZxxl, yang menyarankan untuk menggunakan rdrandinstruksi ini.

Berikut adalah kode sumbernya (dapat dikompilasi oleh Visual Studio):

__declspec(naked) void __fastcall shuffle(unsigned size, int array[])
{
    // fastcall convention:
    // ecx = size
    // edx = array
    _asm
    {
        pushad;             // save registers
        mov edi, edx;       // edi now points to the array

    myloop:
        rdrand eax;         // get a random number
        xor edx, edx;
        div ecx;            // edx = random index in the array

        dec ecx;            // count down
        mov eax, [edi + 4 * ecx];   // swap elements
        xchg eax, [edi + 4 * edx];  // swap elements
        mov [edi + 4 * ecx], eax;   // swap elements
        jnz myloop;

        popad;              // restore registers
        ret;
    }
}

Namun implementasi Fisher-Yates yang lain. Sebagian besar golf dicapai dengan melewati parameter dalam register.

anatolyg
sumber
1
Anda juga bisa menggunakan rdranduntuk omong kosong dan cekikikan.
FUZxxl
@ FuZxxl Saya benar-benar lupa tentang itu! Sayang sekali itu menghilangkan bagian paling menarik tentang jawaban saya ...
anatolyg
9

Jawa, 88 101

Acak Fisher-Yates dasar melakukan trik. Saya merasa itu akan digunakan cukup umum di sini, karena cepat dan mudah diimplementasikan. Ada beberapa loop / tugas yang menjejalkan di sini, tapi jujur ​​tidak terlalu banyak bermain golf; itu hanya singkat secara alami.

void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}

Dengan beberapa jeda baris:

void t(int[]s){
    for(int i=s.length,t,x;
        i>0;
        t=s[x*=Math.random()],
        s[x]=s[i],
        s[i]=t
    )
        x=i--;
}

Ini mengocok di tempat, memodifikasi array asli s[]. Program uji:

public class Shuffle {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        new Shuffle().t(a);
        for(int b:a)
            System.out.print(b+" ");
    }
    void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}
}
Geobit
sumber
1
Tidak, tantangannya menyatakan bahwa Anda dapat menganggapnya " seragam sempurna untuk rentang yang diminta ". Rentang yang diminta Math.random()memiliki ukuran yang merupakan kekuatan dua, jadi ini tidak memenuhi spesifikasi.
Peter Taylor
1
@PeterTaylor Jan's dan Geobits 'interpretasi memang bagaimana saya bermaksud aturan - bahwa Anda tidak perlu khawatir tentang panjang siklus aktual dari PRNG Anda.
Martin Ender
1
@ MartinBüttner panjang siklus bukan masalah di sini - yang dicakup oleh aturan Anda. Kekasaran mengapung adalah.
John Dvorak
3
@TheBestOne Ini satu byte lebih pendek dari satu-satunya solusi python yang saat ini diposting;)
Geobits
1
Tidak lagi! : D
Sp3000
8

Python 2, 86 byte

from random import*
def S(L):i=len(L);exec"i-=1;j=randint(0,i);L[i],L[j]=L[j],L[i];"*i

Ini adalah fungsi yang mengocok array di tempatnya tanpa mengembalikannya, menggunakan implementasi langsung dari shuffle Fisher-Yates . Mendapatkan nomor acak dari Python mahal ...

Terima kasih kepada @xnor dan @colevk untuk kiatnya.

Sp3000
sumber
Ekspresi rentang itu terlihat cukup rumit. Tentunya lebih pendek untuk menghitung mundur secara manual while i:i-=1;...?
xnor
@ xnor Ya itu - terima kasih untuk itu. Saya selalu lupa bahwa whilecenderung lebih pendek daripada foruntuk hal semacam ini ...
Sp3000
1
Awww ... sekarang jawaban Java saya tidak mengalahkan ini. Saya cukup senang untuk waktu yang sangat singkat :(
Geobits
Anda dapat menyimpan 2 byte lainnya dengan membuat i=len(L)dan meletakkan decrement di awal while loop.
colevk
8

J, 45 44 karakter

Ini yang sulit.

<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

Berikut ini penjelasannya:

  1. # y: The penghitungan dari y, yaitu, jumlah elemen dalam y.
  2. ?@# y: Nomor acak yang didistribusikan secara seragam dari rentang 1ke (#y)-1.
  3. x { y: Item dari y at index x.
  4. (<<<x) { y: Semua item kecuali item pada indeks xdalam y.
  5. x , y: y ditambahkan ke x.
  6. x ({ , <^:3@[ { ]) y: Item di index xin y, lalu semua item lainnya.
  7. (?@# ({ , <^:3@[ { ]) ]) yAcak dari y, lalu semua item lainnya.
  8. x {. y: Pertama xitem yang diambil dari y.
  9. x }. y: xItem pertama turun dari y.
  10. x ({. , }.) y: Pertama xitem diambil dari y, maka yang pertama xitem turun dariy
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Pertama xitem diambil dari y, maka yang pertama xitem dari yolahan seperti pada nomor 7.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: Hal yang sama dengan drop yang ditarik untuk menyelamatkan satu karakter.
  13. u/ y: u disisipkan di antara item y.
  14. < y: y kotak .
  15. <"0 y: Setiap item dalam y kotak .
  16. i. y: integer dari 0ke y - 1.
  17. i.@# y: integer dari 0ke (#y) - 1.
  18. (<"0@i.@# , <) y: Integer dari 0ke (#y) - 1setiap kotak dan kemudian ydalam satu kotak. Ini diperlukan karena array dalam J adalah seragam. Sebuah kotak menyembunyikan bentuk isinya.
  19. x u&v y: seperti (v x) u (v y).
  20. > y: y dibuka , yaitu, tanpa kotaknya.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y frasa dari angka 12 diterapkan pada argumennya yang tidak dikotak.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ yfrasa dari nomor 21 disisipkan di antara item dari y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) yfrasa dari nomor 22 diterapkan pada hasil frasa dari nomor 18, atau, permutasi yang seragam dari item y.
FUZxxl
sumber
1
Saya tidak bisa membedakan semua tanda kurung. Dan bertinju tiga <@<@<@[itu juga merupakan misteri ... Menunggu penjelasan. :)
randomra
2
Setelah ini dijelaskan, saya mungkin lebih mungkin untuk memilih jawaban ini ;-)
John Dvorak
@randomra Ini dia.
FUZxxl
@ JanDvorak Apakah penjelasannya memuaskan?
FUZxxl
Penjelasan hebat! Saya tidak tahu tentang semua penggunaan kotak from( {). Dan saya sangat suka &>/trik untuk memanipulasi daftar. Saya yakin saya bisa menggunakannya beberapa kali sebelumnya.
randomra
5

Pyth, 25 byte

Uji di sini.

Namun implementasi Fisher-Yates yang lain. Pada dasarnya sama dengan solusi python @ Sp3000, hanya di pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Terima kasih kepada @Jakube untuk trik swapping

<implicit>    Q=input()
FNrlQ1        For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
 KON          K = random int 0-N
 J@QN         J=Q[N]
 <space>      Suppress print
 XXQN@QKKJ    Swap K and J
)             End for
Q             Print Q
Maltysen
sumber
Anda dapat menyimpan dua byte dengan menggabungkan dua tugas daftar itu: `XXQN @ QKKJ` alih-alih` XQN @ QK XQKJ`.
Jakube
@ Jakube terima kasih atas tipnya. Saya tahu pasti ada cara untuk menukar nilai dalam daftar, dan ini sangat cerdas. Anda harus menambahkannya ke daftar tips.
Maltysen
4

Perl, 68 56 44

Seperti banyak solusi lain, ini menggunakan algoritma Fisher-Yates .

Menggunakan komentar nutki , 12 karakter disimpan dengan menggunakan $_alih-alih $idan melakukan operasi dalam indeks array.

44:

sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}

56:

sub f{$i=@_;$j=int(rand$i),@_[$i,$j]=@_[$j,$i]while$i--}

Ini codegolf pertamaku.

Bonsaigin
sumber
Bukan awal yang buruk, saya tidak tahu bahwa Anda dapat menggunakan @_[...]sebagai nilai seperti itu. Dapat bermain golf lebih jauh sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}.
nutki
3

C, 63 61 60 byte

i,t;s(a,m)int*a;{for(;m;a[m]=t)t=a[i=rand()%m--],a[i]=a[m];}

Hanya implementasi langsung dari Fischer-Yates yang mengurutkan array yang diberikan pada tempatnya. Mengkompilasi dan menghubungkan dengan sangat baik dengan kompiler studio visual (vs2013, belum menguji versi lain) dan Intel Compiler. Tanda tangan fungsi tampak bagus s(int array[], int length). Saya terkesan secara sah dengan mengalahkan Python dan Ruby.

Asumsi srand()ini dipanggil dan rand () diimplementasikan dengan benar, tetapi saya percaya aturan ini memungkinkan untuk itu:

You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval

Versi yang diformat dengan baik:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
pseudonim117
sumber
Saya pikir sudah cukup untuk membuat header fungsi s(a,m)*a{, tapi saya tidak yakin dan tidak ingin menguji juga. Anda mungkin ingin melakukan- xorswap, seperti di a[i]^=a[m]^=a[i]^=a[m]. Ini juga menghindari keharusan untuk menyatakan t.
FUZxxl
@ FuZxxl Saya percaya xor swap menyebabkan masalah jika i==m.
Geobits
@Geobits memang. Saya melewatkan kemungkinan itu.
FUZxxl
Saya hanya mencoba mencari tahu mengapa itu tidak berhasil ... harus ingat itu. Saya juga perlu s(a,m)int*auntuk studio visual dan kompiler intel. Tidak memiliki gcc atau dentang yang diinstal untuk menguji, tetapi saya menganggap mereka juga akan mengeluh.
pseudonym117
Ini sangat mengesankan golf. Setelah mencoba banyak modifikasi yang tidak menyimpan apa pun, saya berhasil melihat cara untuk menyimpan 2 karakter. Jika Anda mengubah urutan swap sehingga pernyataan swap pertama menjadi t=a[i], Anda kemudian dapat memindahkan i=rand()%m--pernyataan di dalam sebagai indeks array.
Runer112
3

Oktaf, 88 77 byte

function s=r(s)for(i=length(s):-1:1)t=s(x=randi(i));s(x)=s(i);s(i)=t;end;end

Namun implementasi Fisher-Yates yang lain ... Harus cukup mudah jika saya menambahkan garis pengembalian dan spasi yang biasa:

function s=r(s)
  for(i=length(s):-1:1) # Counting down from i to 1
    t=s(x=randi(i));    # randi is builtin number generator for an int from 0 to i
    s(x)=s(i);
    s(i)=t;
  end
end

Kata kunci "akhir" benar-benar membunuh skor golf di sini, sayangnya. Hai, saya bisa menggunakan "end" daripada "endfor" dan "endfunction"!

dcsohl
sumber
1
Hanya FYI, "byte" tidak benar-benar dibutuhkan oleh kode, itu hanya membuat yakin ada adalah judul, yang berisi tanda koma (untuk memisahkan bahasa) dan setidaknya satu angka setelah koma, dan kemudian hanya memilih yang terakhir nomor yang tidak dicoret. Memiliki "byte" di sana masih bagus. ;)
Martin Ender
1
Anda bisa menghemat 1 byte dengan menggunakan numelbukan lenght. Sebagai bonus, program Anda juga akan bekerja dengan array 2-D alias matriks;)
paul.oderso
2

Java 8, 77

(x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};

Ini adalah lambda mengambil int[]dan mengembalikan kekosongan. Upaya pertama saya sepertinya tidak terlalu menarik, jadi saya memutuskan untuk mengeluarkannya dengan melemparkan pengecualian.

Program uji:

interface shuff {
    void shuff(int[] x);
}
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        shuff s = (x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};
        int[] x = {3, 9, 2, 93, 32, 39, 4, 5, 5, 5, 6, 0};
        try {
            s.shuff(x);
        } catch(ArrayIndexOutOfBoundsException _) {}
        for(int a:x) System.out.println(a);
    }
}
feersum
sumber
1
Bukankah curang menggunakan lambda untuk berkeliling harus menulis tanda tangan fungsi, ketika Anda harus menyediakan delegasi untuk menggunakan lambda di mana saja? Juga ... tidak bisakah kamu menjatuhkan tanda kurung Math.random()?
Rawling
1
@Rawling Anda dapat memberikan suara di pertanyaan meta ini . Saat ini, ada 9 suara yang mendukung lambdas, dan 0 menentang. Ya, tanda kurung dapat dihapus.
feersum
Huh, jika ada meta pos dan konsensus sejauh ini maka tembaklah. (Dan nikmati skor golf dua-lebih rendah pada saya: p)
Rawling
3
Saya pikir, tidak adil bagi fungsi untuk berhenti dengan pengecualian dalam kasus normal, bukan?
Qwertiy
1
@ Qwertiy Untuk masing-masing sendiri ... Anda pikir itu tidak adil, saya pikir itu hebat.
feersum
2

Golflua, 37

Bagaimana cara menjalankan Golflua?

~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$

Input diberikan sebagai tabel dalam variabel X. Tabel diacak di tempatnya.

Contoh penggunaan:

> X={0,-45,8,11,2}
> ~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$
> w(T.u(X))
-45 0 8 11 2
mniip
sumber
2

R, 79 byte

f=function(x){n=length(x);for(i in 1:n){j=sample(i:n,1);x[c(i,j)]=x[c(j,i)]};x}

Ini adalah implementasi langsung dari shuffle Fisher-Yates. Fungsi R samplemenggambar sampel acak sederhana dengan ukuran tertentu dari vektor yang diberikan dengan probabilitas yang sama. Di sini kita menggambar sampel acak ukuran 1 pada setiap iterasi dari bilangan bulat i, ..., n. Sebagaimana dinyatakan dalam pertanyaan, ini dapat dianggap sebagai O (1), jadi dalam semua implementasi ini harus O (N).

Alex A.
sumber
2

Matlab, 67

Juga menerapkan Fisher-Yates.

a=input('');n=numel(a);for i=1:n;k=randi(i);a([i,k])=a([k,i]);end;a

Saya pikir itu terlalu buruk saya tidak bisa menggunakan randpermfungsi Matlab . Tetapi setelah beberapa mengutak-atik, saya pikir saya mungkin melihat sumber randpermuntuk melihat bagaimana hal itu dilakukan, dan saya heran melihat bahwa hanya ada satu baris: [~,p] = sort(rand(1,n))=)

cacat
sumber
2

Perl, 44

sub f{($_[$x],$_)=($_,$_[$x=rand++$i])for@_}

Perl lainnya dalam 44 karakter. Contoh penggunaan:

@x=(1..9);f(@x);print@x
nutki
sumber
2

Mathematica, 82 90 83 93 byte

Catatan: Variasi ini shuffle Fisher-Yates sebenarnya adalah solusi Martin Büttner, dengan beberapa kode pengurang oleh alephalpha. sadalah array input. Tidak ada yang mewah-smancy, tetapi terkadang hal-hal sederhana adalah yang paling sulit dipahami.

f@s_:=(a=s;m=Length@a;Do[t=a[[r=RandomInteger@{1,m-1}]];a[[r]]=a[[m]]; a[[m]]=t,{n,1,m-1}];a)
DavidC
sumber
Anda bisa menggunakannya di Dosini. Itu lebih pendek dari While.
alephalpha
2

Ruby, 57 byte

->a{a.size.times{|i|j=rand(i+1);a[i],a[j]=a[j],a[i]};p a}

Input (sebagai fungsi lambda):

f.([1,2,3,4,5])

Keluaran:

[2, 1, 4, 3, 5]
Nol Serat
sumber
2

TI-BASIC, 46 byte

For(X,dim(L1),2,-1:randInt(1,X→Y:L1(X→Z:L1(Y→L1(X:Z→L1(Y:L1

1   111   2  1111112       1111112 111112 1112 111112 1112

Sumber untuk jumlah byte

Ypnypn
sumber
1
Anda melewatkan End.
lirtosiast
2

K, 31 karakter

f:{{l[i:x,1?x]:l@|i}'|!#l::x;l}

Tidak sesingkat yang saya pasang sebelumnya (yang didiskualifikasi) ... oh well.

Ini adalah shuffle Fisher-Yates dasar. Ini dibangun dengan banyak bantuan dari milis Kona .

kirbyfan64sos
sumber
2

JavaScript (ES6), 66

Fungsi ini mengocok array di tempatnya. Ini juga mengembalikan array produk sampingan yang BUKAN output yang dikocok dan tidak harus dipertimbangkan.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)
edc65
sumber
2

MATL , 16 byte

XH`HnYr&)XHxvHHn

Cobalah online!

Fisher-Yates dalam MATL. Hampir sepertiga dari program ini dikhususkan untuk surat ituH , yang sesuai dengan fungsi clipboard di MATL.

Pada dasarnya, Hsimpan barang-barang yang tidak digunakan dari input, sementara tumpukan melacak daftar acak.

Sanchises
sumber
2

Japt, 12

rÈiMqZÄ Y}[]

Cobalah!

-10 (sekitar setengah;) terima kasih kepada @Shaggy!

Saya ingin mencoba bahasa golf, dan penerjemah Japt memiliki dokumentasi yang baik dan cara untuk mencoba berbagai hal di browser.

Di bawah ini adalah strategi yang saya ambil:

  • Kurangi penyemaian input dengan array kosong
  • Di setiap langkah, cari slot acak untuk memasukkan elemen saat ini
dana
sumber
1
Selamat datang di Japt, senang Anda bersama kami. Saya pikir ini berfungsi selama 9 byte, menggunakan metode yang sama. Namun, jika RNG tidak memuaskan, cobalah ini .
Shaggy
@Shaggy - Terima kasih atas tipsnya! :) Saya akhirnya menggunakan versi 2 solusi Anda yang sedikit dimodifikasi. Karena parameter ke-3 dari fungsi pengurangan adalah indeks, kita sudah tahu panjangnya.
dana
1

Javascript ES6, 69

a=>{m=a.length;while(m)[a[m],a[i]]=[a[i=~~(Math.random()*m--)],a[m]]}

Ini Fisher – Yates.

PS: Dapat diuji di Firefox

Qwertiy
sumber
@ MartinBüttner, hapus itu :)
Qwertiy
1

Pyth, 27 byte

Uji di sini

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

Ini adalah implementasi dari shuffle Fisher-Yates tambahan, disebutkan kedua di sini .

isaacg
sumber
1

Haskell, 170

import System.Random
import Data.Array.IO
s a=do(_,n)<-getBounds a;sequence$map(\i->do j<-randomRIO(i,n);p<-a%i;q<-a%j;writeArray a j p;return q)[1..n]where(%)=readArray

Solusi Fisher-Yates lain yang terinspirasi oleh algoritma di https://wiki.haskell.org/Random_shuffle .

s adalah fungsi yang memiliki tanda tangan: IOArray Int a -> IO [a]

Jmac
sumber
1

CJam - 30

q~_,,W%{_I=I)mr:J2$=@I@tJ@t}fI

Cobalah di http://cjam.aditsu.net/

Input contoh: [10 20 30 40 50]
Contoh output: 3020401050(tambahkan a pdi akhir kode untuk pencetakan cantik)

Jika kode diizinkan untuk mengambil input dari tumpukan (seperti fungsi), maka 2 karakter pertama dapat dihapus, mengurangi ukuran menjadi 28.

Penjelasan:

Kode lebih panjang daripada yang saya harapkan, karena kurangnya operator "swap" untuk array
(akan diimplementasikan kemudian: p)

q~            read and evaluate the input (let's call the array "A")
_,,           make an array [0 1 2 ... N-1] where N is the size of A
W%            reverse the array, obtaining [N-1 ... 2 1 0]
{…}fI         for I in this array
    _I=       push A[I]
    I)mr:J    push a random number from 0 to I (inclusive) and store it in J
              stack: A, A[I], J
    2$=       get A[J]
    @I@t      set A[I] = A[J]
              stack: former A[I], A
    J@t       set A[J] = former A[I]
aditsu
sumber
Seperti yang disebutkan dalam komentar, saya khawatir ini tidak valid. Paling tidak _adalah O (N) (di dalam lingkaran O (N)). Sayangnya, saya tidak melihat cara untuk mengatasi itu di CJam.
Martin Ender
Daftar ditangani seperti objek yang tidak dapat diubah, sehingga duplikasi hanya diterapkan sebagai duplikasi referensi. Sebenarnya itu tyang membunuhnya, karena tidak dapat mengubah daftar dan sekarang harus membuat salinan.
Runer112
@ MartinBüttner Saya akan memposting hal yang sama dengan Runer112; ya mungkin ada masalah dengan t, saya ingin memperbaikinya di versi mendatang ..
aditsu
Jadi kode ini mengikuti semangat pertanyaan, tetapi bukan "surat", karena masalah implementasi bahasa internal.
aditsu
1

JavaScript (ES 6), 61

S=a=>(a.map((c,i)=>(a[i]=a[j=Math.random()*++i|0],a[j]=c)),a)

Anda dapat mengujinya di sini hanya dengan menambahkan baris yang mengatakan shuffle = S(khusus Firefox).

core1024
sumber
1

STATA, 161

di _r(s)
set ob wordcount($s)
token $s
g a=0
foreach x in $s{
gl j=floor(runiform()*_n)+1
replace a=`$j' if word($s,_n)=`x'
replace a=`x' if word($s,_n)=`$j'
}
l

Mengharapkan input sebagai angka yang dipisahkan ruang. Saya bisa menghapus header dan nomor observasi dari output jika Anda mau, tetapi jika tidak, ini lebih pendek.

tanda
sumber
Ada apa _nini?
Martin Ender
_n adalah jumlah pengamatan saat ini.
menandai
1

Java, 93 byte

a->{for(int b=0,c,d=0,e=a.length;b<e;c=a[b],a[b]=a[d],a[d]=c,b++,d=b)d+=Math.random()*(e-b);}

Contoh penggunaan: http://ideone.com/RqSMnZ

TheNumberOne
sumber
1

SQF, 91 byte

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i
Suram
sumber
1
Ini bias (lihat "swap (i <-> acak)" di Will It Shuffle), tetapi Anda dapat mengubahnya menjadi Fisher-Yates (yang tidak bias) dengan menggantinya %xdengan %i.
Martin Ender