tło

Mam kolekcję „skarpet w dni powszednie”, czyli siedem par skarpet oznaczonych dniami tygodnia. Kiedy myję skarpetki, kończą się w kupie i muszę je ułożyć w odpowiednie pary, zanim włożę je do szafy. Moją strategią jest wyciąganie jednej losowej skarpety ze stosu i wkładanie jej do szuflady. Ilekroć w szufladzie znajduje się pasująca para skarpet, wiążę je ze sobą i wkładam do szafy. Twoim zadaniem jest symulacja tego losowego procesu i zwrócenie liczby losowań wymaganych do znalezienia pierwszej pasującej pary.

Wejście

Twoje dane wejściowe to liczba całkowita N ≥ 1 . Reprezentuje „liczbę dni w tygodniu”: na stosie znajduje się N par skarpet, a każda para ma inną etykietę. W razie potrzeby możesz również wziąć ziarno PRNG jako dane wejściowe.

Wynik

Twój wynik to liczba skarpet, które muszę narysować, zanim zostanie znaleziona pierwsza pasująca para. Na przykład, jeśli pierwsze dwie skarpety już tworzą pasującą parę, wynikiem jest 2.

Oczywiście dane wyjściowe są losowe i zależą od kolejności rysowania. Zakładamy, że wszystkie zamówienia na rysowanie są jednakowo prawdopodobne , więc za każdym razem, gdy zostanie wyciągnięta skarpeta, wybór jest jednolity i niezależny od wszystkich innych wyborów.

Przykład

Niech N = 3 , abyśmy mieli w sumie 6 skarpet oznaczonych AABBCC . Jeden z możliwych przebiegów „protokołu rysowania skarpet” jest następujący:

       | 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

Pierwsza pasująca para została znaleziona po narysowaniu drugiej B , która była trzecią skarpetą do narysowania, więc prawidłowe wyjście to 3.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Dane wejściowe i wyjściowe mogą mieć dowolny rozsądny format, w tym jednoargumentowy (ciąg znaków 1).

Możesz założyć, że wbudowana w Twój język RNG jest idealna. Nie musisz tak naprawdę symulować protokołu rysowania skarpet, o ile twoje wyniki mają prawidłowy rozkład prawdopodobieństwa.

"Przypadki testowe"

Oto przybliżone prawdopodobieństwo wszystkich wyjść dla wejścia 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

Aby przetestować swoje rozwiązanie, możesz uruchomić je, powiedzmy, 40 000 razy i sprawdzić, czy rozkład wyjściowy jest dość zbliżony do tego.

Galaretka , 8 bajtów

ḤX€Ṛ<RTḢ

Wypróbuj online! lub sprawdź rozkład dla N = 7 .

tło

Niech n będzie liczbą par; są 2 pojedyncze skarpety.

Do pierwszego losowania są 2n skarpetek, a 0 z nich dałoby pasującą parę. Dlatego prawdopodobieństwo sukcesu wynosi 0 / 2n = 0 .

Ponieważ pierwsze losowanie się nie powiodło, na stosie znajdują się 2n - 1 skarpet, a 1 z nich dałoby pasującą parę. Dlatego prawdopodobieństwo sukcesu wynosi 1 / (2n - 1) .

Jeśli drugie losowanie się nie powiedzie, na stosie znajdują się 2n - 2 skarpetki, a 2 z nich dają pasującą parę. Dlatego prawdopodobieństwo sukcesu wynosi 2 / (2n - 2) .

Ogólnie rzecz biorąc, jeśli pierwsze k losowanie zakończyło się niepowodzeniem, na stosie znajdują się skarpety 2n - k, a 2 z nich dałyby pasującą parę. Dlatego prawdopodobieństwo sukcesu wynosi k / (2n - k) .

Wreszcie, jeśli żadne z pierwszych n losowań nie zakończyło się sukcesem, na stosie znajdują się skarpety 2n-k i wszystkie z nich dałyby pasującą parę. Dlatego prawdopodobieństwo sukcesu wynosi n / (2n - n) = 1 .

Jak to działa

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

Galaretka, 8 bajtów

Rx2ẊĠṪ€Ṃ

Wypróbuj 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

Aby to sprawdzić, oto wersja, która wyświetla zarówno pożądane dane wyjściowe, jak i wynik operacji „losowej listy” (aby zobaczyć, w jakiej kolejności zostały pobrane skarpety).

Python, 66 bajtów

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

Dennis wymyślił sprytny sposób na zmianę układu, oszczędzając 5 bajtów.

MATL , 16 15 bajtów

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

Wypróbuj online! Lub obserwuj rozkład empiryczny dla 1000 próbek w przypadku N = 7 (zajmuje to chwilę).

To bezpośrednio generuje zmienną losową reprezentującą wynik na podstawie jego rozkładu prawdopodobieństwa. Niech N będzie liczbą par skarpet i niech p ( k ) oznacza prawdopodobieństwo, że k -te losowanie zakończy się powodzeniem, pod warunkiem, że k -1 losowanie nie zakończyło się powodzeniem. Następnie (patrz również tutaj ):

• p (1) to oczywiście 0. Nie możesz mieć pary z jedną skarpetą.
• p (2) wynosi 1 / (2 * N -1). Przy drugim losowaniu jest jedna zwycięska skarpeta, którą można wybrać z 2 pozostałych skarpet N- 1.
• p (3) wynosi 2 / (2 * N- 2). W trzecim losowaniu są 2 zwycięskie skarpetki z 2 * N −2. Liczba zwycięskich skarpet wynosi 2, ponieważ dwie skarpetki otrzymane po drugim losowaniu były różne.
• Ogólnie, z tego samego rozumowania, p ( k ) jest ( k −1) / (2 * N - k +1)
• Zgodnie z powyższym wzorem p ( N +1) wynosi 1. Jeśli dojdziesz do losowania N + 1, masz gwarancję sukcesu.

Tak więc kod iteruje maksymalnie N losowań +1. Przy k-tym losowaniu generowana jest zmienna losowa, która jest równa 1 z prawdopodobieństwem ( k -1) / (2 * N - k ) lub 0 w przeciwnym razie. Ilekroć zmienna losowa jest równa 1 (losowanie się powiodło), proces zatrzymuje się, a bieżące k jest wyprowadzane.

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 bajtów

EZ@G\&=XRafX<

Wypróbuj online! Lub obserwuj rozkład empiryczny dla 4000 próbek w przypadku N = 7 (zajmuje to trochę czasu).

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 bajtów

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

Wyjaśnienie

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 bajtów

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

Sprawdź to tutaj.

Python 3, 142 105 104 bajtów

Dzięki Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ za oszczędność jednego bajtu!

Moja pierwsza odpowiedź:

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

Moja nowa odpowiedź:

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

Oba wychodzą z NameErrorwłączonym s.

R, 49

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

Jestem pewien, że musi istnieć lepszy sposób na zrobienie tego w R! Próbowałem zrobić coś mądrzejszego, ale to nie zadziałało.

Edycja: Ulepszony przez @bouncyball, ponieważ nie musi to być funkcja.

Python 2, 101 bajtów

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

VBA, 61 bajtów

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

- modeluje prawdopodobieństwo przesunięcia dopasowania skarpety przy podanym wcześniej braku dopasowania. W punkcie oceny K jest „skarpetkami w ręku”, więc liczba losowań jest jeszcze jedna.

Pyth, 14 bajtów

lhfnT{T._.S*2S

Wyjaśnienie:

       ._        #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