Latar Belakang

Saya memiliki koleksi "kaus kaki hari kerja", yang merupakan tujuh pasang kaus kaki yang dilabeli oleh hari-hari dalam seminggu. Ketika saya mencuci kaus kaki saya, mereka berakhir di tumpukan, dan saya harus mengaturnya menjadi pasangan yang benar sebelum memasukkannya ke dalam lemari. Strategi saya adalah menarik satu kaus kaki acak dari tumpukan sekaligus dan meletakkannya di laci. Setiap kali ada sepasang kaus kaki yang serasi di laci, aku mengikatnya dan meletakkannya di lemari. Tugas Anda adalah untuk mensimulasikan proses acak ini dan mengembalikan jumlah undian yang diperlukan untuk menemukan pasangan yang cocok pertama.

Memasukkan

Input Anda adalah bilangan bulat N ≥ 1 . Ini mewakili "jumlah hari dalam seminggu": ada N pasang kaus kaki di tumpukan, dan masing-masing pasangan memiliki label yang berbeda. Jika perlu, Anda juga dapat mengambil seed PRNG sebagai input.

Keluaran

Output Anda adalah jumlah kaus kaki yang harus saya gambar sebelum pasangan yang cocok pertama kali ditemukan. Misalnya, jika dua kaus kaki pertama sudah membentuk pasangan yang cocok, hasilnya adalah 2.

Tentu saja, hasilnya acak, dan tergantung pada urutan gambar. Kami berasumsi bahwa semua pesanan penarikan memiliki kemungkinan yang sama , sehingga setiap kali kaus kaki ditarik, pilihannya seragam dan independen dari semua pilihan lainnya.

Contoh

Misalkan N = 3 , sehingga kita memiliki total 6 kaus kaki, berlabel AABBCC . Salah satu kemungkinan menjalankan "protokol sock-drawing" adalah sebagai berikut:

       | Pile   | Drawer | Pairs
Begin  | AABBCC | -      | -
Draw B | AABCC  | B      | -
Draw C | AABC   | BC     | -
Draw B | AAC    | C      | BB
Draw A | AC     | AC     | BB
Draw A | C      | C      | AA BB
Draw C | -      | -      | AA BB CC

Pasangan yang cocok pertama ditemukan setelah menggambar B kedua , yang merupakan kaus kaki ketiga yang harus ditarik, sehingga output yang benar adalah 3.

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Input dan output dapat dalam format yang masuk akal, termasuk unary (string 1s).

Anda dapat berasumsi bahwa RNG bawaan bahasa Anda sempurna. Anda tidak harus benar-benar mensimulasikan protokol sock-drawing, selama output Anda memiliki distribusi probabilitas yang benar.

"Uji kasus"

Berikut adalah perkiraan probabilitas semua keluaran untuk input N = 7 :

Output       2     3     4     5     6     7     8
Probability  0.077 0.154 0.210 0.224 0.186 0.112 0.037

Untuk menguji solusi Anda, Anda dapat menjalankannya untuk, katakanlah, 40.000 kali dan lihat apakah distribusi output cukup dekat dengan ini.

Jelly , 8 byte

ḤX€Ṛ<RTḢ

Cobalah online! atau verifikasi distribusi untuk N = 7 .

Latar Belakang

Biarkan n menjadi jumlah pasangan; ada 2n kaus kaki individu.

Untuk undian pertama, ada 2n kaus kaki dan 0 dari mereka akan menghasilkan pasangan yang cocok. Oleh karena itu, probabilitas keberhasilan adalah 0 / 2n = 0 .

Karena undian pertama tidak berhasil, ada 2n - 1 kaus kaki di tumpukan dan 1 dari mereka akan menghasilkan pasangan yang cocok. Oleh karena itu, probabilitas keberhasilan adalah 1 / (2n - 1) .

Jika undian kedua tidak berhasil, ada 2n - 2 kaus kaki di tumpukan dan 2 dari mereka akan menghasilkan pasangan yang cocok. Oleh karena itu, probabilitas keberhasilan adalah 2 / (2n - 2) .

Secara umum, jika penarikan pertama k tidak berhasil, ada 2n - k kaus kaki pada tumpukan dan 2 dari mereka akan menghasilkan pasangan yang cocok. Oleh karena itu, probabilitas keberhasilan adalah k / (2n - k) .

Akhirnya, jika tidak ada yang pertama n menarik berhasil, ada 2n - k kaus kaki di tumpukan dan mereka semua akan menghasilkan pasangan yang cocok. Oleh karena itu, probabilitas keberhasilan adalah n / (2n - n) = 1 .

Bagaimana itu bekerja

ḤX€Ṛ<RTḢ  Main link. Argument: n

Ḥ         Unhalve; yield 2n.
 X€       Map `random draw' over [1, ..., 2n], pseudo-randomly choosing an integer
          from [1, ..., k] for each k in [1, ..., 2n].
   Ṛ      Reverse the resulting array.
     R    Range; yield [1, ..., n].
    <     Perform vectorized comparison.
          Comparing k with the integer chosen from [1, ..., 2n - (k - 1)] yields 1
          with probability (k - 1) / (2n - (k - 1)), as desired.
          The latter half of elements of the left argument do not have a counter-
          part in the right argument, so they are left untouched and thus truthy.
      T   Truth; yield all indices of non-zero integers.
       Ḣ  Head; extract the first one.

Jelly, 8 byte

Rx2ẊĠṪ€Ṃ

Cobalah online!

R    generate [1, 2, ..., n]
x2   duplicate every element (two socks of each pair)
Ẋ    shuffle the list, to represent the order in which socks are drawn
Ġ    group indices by value. this will produce a list of pairs of indices;
       each pair represents the point in time at which each of the corresponding
       socks were drawn
Ṫ€   take the last element of each pair. this returns an array of n integers
       which represent the points in time at which a matching sock was drawn
Ṃ    minimum, find the first point at which a matching sock was drawn

Untuk memverifikasi, berikut adalah versi yang menampilkan keluaran yang diinginkan dan hasil dari operasi "daftar acak" (untuk melihat urutan kaus kaki yang digunakan).

Python, 66 byte

from random import*
f=lambda n,k=1:k>randint(1,n*2)or-~f(n-.5,k+1)

Dennis memikirkan cara cerdas untuk mengatur ulang berbagai hal, menghemat 5 byte.

MATL , 16 15 byte

Q:"r@qGEy-/<?@.

Cobalah online! Atau amati distribusi empiris untuk 1000 sampel dalam kasus N = 7 (butuh beberapa saat).

Ini secara langsung menghasilkan variabel acak yang mewakili hasil, berdasarkan distribusi probabilitasnya. Misalkan N adalah jumlah pasangan kaus kaki, dan misalkan p ( k ) menunjukkan probabilitas bahwa undian k -th berhasil, dikondisikan pada fakta bahwa undian k -1-th tidak berhasil. Kemudian (lihat juga di sini ):

• p (1) jelas 0. Anda tidak dapat memiliki sepasang dengan kaus kaki tunggal.
• p (2) adalah 1 / (2 * N −1). Pada undian kedua ada satu kaus kaki pemenang yang dapat dipilih dari 2 * N −1 kaus kaki yang tersisa.
• p (3) adalah 2 / (2 * N −2). Pada undian ketiga ada 2 kaus kaki menang dari 2 * N −2. Jumlah kaus kaki yang menang adalah 2 karena dua kaus kaki yang Anda dapatkan setelah undian kedua berbeda.
• Secara umum, dengan alasan yang sama, p ( k ) adalah ( k −1) / (2 * N - k +1)
• Dengan rumus di atas, p ( N +1) adalah 1. Jika Anda mendapatkan N + 1-th menarik Anda dijamin untuk sukses itu.

Jadi, kode ini berulang untuk maksimum penarikan N +1. Pada undian k -th, dihasilkan suatu variabel acak yang sama dengan 1 dengan probabilitas ( k -1) / (2 * N - k ), atau 0 sebaliknya. Setiap kali variabel acak sama dengan 1 (undian telah berhasil) proses berhenti dan k saat ini adalah output.

Q:      % Input N implicitly. Generate [1 2 ... N+1] (values of draw index, k)
"       % For each
  r     %   Random variable uniformly distributed on the interval (0,1)
  @q    %   Push iteration index, k-1
  GE    %   Push 2*N
  y     %   Duplicate: push k-1 again
  -     %   Subtract: gives 2*N-k+1
  /     %   Divide: gives (k-1)/(2*N-k+1)
  <     %   Push 1 if random value is less than (k-1)/(2*N-k+1), 0 otherwise
  ?     %   If we got a 1
    @   %     Push k
    .   %     Break loop
        %   End if implicitly
        % End loop implicitly
        % Display implicitly

MATL , 14 13 byte

EZ@G\&=XRafX<

Cobalah online! Atau amati distribusi empiris untuk 4000 sampel dalam kasus N = 7 (butuh beberapa saat).

E      % Input N implicitly. Multiply by 2
Z@     % Random permutation of [1 2 ... 2*N]
G\     % Modulo N: random permutation of [0 0 1 1 ... N-1 N-1]
&=     % Compare all pairs for equality. Gives an N×N matrix
XR     % Upper triangular part excluding the diagonal
a      % True for each column if it contains at least one true entry
f      % Get indices of true values
X<     % Take minimum. Implicitly display

JavaScript, 77 73 byte

n=>{p={};for(i=n;i--;p[i]=2);while(--p[n*Math.random()|0])i++;return i+2}

Penjelasan

var f = (n) => {
    var index;      // used first to initialize pile, then as counter
    var pile = {};  // sock pile

    // start with index = n
    // check that index > 0, then decrement
    // put 2 socks in pile at index
    for(index = n; index--; pile[index] = 2);
    // index is now -1, reuse for counter

    // pick random sock out of pile and decrement its count
    // continue loop if removed sock was not the last
    while(--pile[n * Math.random() | 0]) {
        index++;    // increment counter
    }
    // loop finishes before incrementing counter when first matching pair is removed
    // add 1 to counter to account for initial value of -1
    // add 1 to counter to account for drawing of first matching pair
    return index + 2;
};

CJam, 17 byte

ri,2*mr{L+:L(&}#)

Uji di sini.

Python 3, 142 105 104 byte

Berkat Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ karena telah menghemat satu byte!

Jawaban pertama saya:

import random 
i=[x/2 for x in range(int(2*input()))]
d=[]
a=0
random.shuffle(i)
while 1:
 b=i.pop()
 if b in d:
  print(a)
  s
 d=d+[b]
 a+=1

Jawaban baru saya:

from random import*
i=range(int(input()))*2
shuffle(i)
j=0
for x in i:
 if x in i[:j]:print(1+j)+s
 j+=1

Keduanya keluar dengan NameErroron s.

R, 49

N=scan();which(duplicated(sample(rep(1:N,2))))[1]

Saya yakin pasti ada cara yang lebih baik untuk melakukan ini di R! Saya mencoba melakukan sesuatu yang lebih pintar tetapi tidak berhasil.

Sunting: Ditingkatkan oleh @bouncyball karena tidak harus menjadi fungsi.

Python 2, 101 byte

from random import*
d=[]
p=range(input())*2
shuffle(p)
while list(set(d))==d:d+=p.pop(),
print len(d)

VBA, 61 byte

Function K(D):While 2*D-K>K/Rnd:K=K+1:Wend:K=K+1:End Function

- memodelkan probabilitas pergeseran pertandingan kaus kaki karena kegagalan sebelumnya untuk mencocokkan. Pada titik evaluasi, K adalah "kaus kaki di tangan", jadi nomor undian adalah satu lagi.

Pyth, 14 byte

lhfnT{T._.S*2S

Penjelasan:

       ._        #Start with a list of all prefixes of
         .S      #a randomly shuffled
           *2S   #range from 1 to input (implicit), times 2.
  f              #filter this to only include elements where
   nT{T          #element is not equal to deduplicated self (i.e. it has duplicates)
lh               #print the length of the first element of that filtered list