Hintergrund

Ich habe eine Sammlung von "Wochentagssocken", bei denen es sich um sieben Paar Socken handelt, die nach Wochentagen gekennzeichnet sind. Wenn ich meine Socken wasche, landen sie auf einem Stapel, und ich muss sie in die richtigen Paare sortieren, bevor ich sie in den Schrank lege. Meine Strategie ist es, eine zufällige Socke nach der anderen vom Stapel zu ziehen und in eine Schublade zu legen. Immer wenn es ein passendes Paar Socken in der Schublade gibt, binde ich sie zusammen und lege sie in den Schrank. Ihre Aufgabe ist es, diesen zufälligen Prozess zu simulieren und die Anzahl der Ziehungen zurückzugeben, die erforderlich sind, um das erste passende Paar zu finden.

Eingang

Ihre Eingabe ist eine ganze Zahl N ≥ 1 . Es stellt die "Anzahl der Tage in einer Woche" dar: Es befinden sich N Paar Socken auf dem Stapel, und jedes Paar hat ein eigenes Etikett. Bei Bedarf können Sie auch einen PRNG-Startwert als Eingabe verwenden.

Ausgabe

Ihre Ausgabe ist die Anzahl der Socken, die ich ziehen muss, bevor das erste passende Paar gefunden wird. Wenn beispielsweise die ersten beiden Socken bereits ein übereinstimmendes Paar bilden, lautet die Ausgabe 2.

Natürlich ist die Ausgabe zufällig und hängt von der Zeichenreihenfolge ab. Wir gehen davon aus, dass alle Zeichenreihenfolgen gleich wahrscheinlich sind , sodass die Auswahl bei jedem Ziehen einer Socke einheitlich und unabhängig von allen anderen Optionen ist.

Beispiel

Es sei N = 3 , so dass wir insgesamt 6 Socken mit der Bezeichnung AABBCC haben . Ein möglicher Durchlauf des "Strumpfziehprotokolls" ist wie folgt:

       | 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

Das erste übereinstimmende Paar wurde nach dem Zeichnen des zweiten B gefunden , das die dritte zu zeichnende Socke war, sodass die richtige Ausgabe vorliegt 3.

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Eingabe und Ausgabe können in jedem vernünftigen Format erfolgen, einschließlich unär (Zeichenfolge von 1s).

Sie können davon ausgehen, dass das in Ihrer Sprache integrierte RNG perfekt ist. Sie müssen das Strumpfziehprotokoll nicht wirklich simulieren, solange Ihre Ausgaben die richtige Wahrscheinlichkeitsverteilung haben.

"Testfälle"

Hier sind die ungefähren Wahrscheinlichkeiten aller Ausgänge für den Eingang 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

Um Ihre Lösung zu testen, können Sie sie beispielsweise 40.000 Mal ausführen und feststellen, ob die Ausgabeverteilung annähernd in der Nähe liegt.

Gelee , 8 Bytes

ḤX€Ṛ<RTḢ

Probieren Sie es online! oder überprüfen Sie die Verteilung für N = 7 .

Hintergrund

Sei n die Anzahl der Paare; Es gibt 2n Einzelsocken.

Bei der ersten Ziehung gibt es 2n Socken und 0 davon würden ein passendes Paar ergeben. Daher ist die Erfolgswahrscheinlichkeit 0 / 2n = 0 .

Da die erste Ziehung nicht erfolgreich war, befinden sich 2n - 1 Socken auf dem Stapel und 1 davon würde ein passendes Paar ergeben. Daher beträgt die Erfolgswahrscheinlichkeit 1 / (2n - 1) .

Wenn die zweite Ziehung nicht erfolgreich war, befinden sich 2n - 2 Socken auf dem Stapel und 2 von ihnen würden ein passendes Paar ergeben. Daher beträgt die Erfolgswahrscheinlichkeit 2 / (2n - 2) .

Wenn die ersten k Draws nicht erfolgreich waren, befinden sich 2n - k Strümpfe auf dem Stapel und 2 von ihnen würden ein passendes Paar ergeben. Daher ist die Erfolgswahrscheinlichkeit k / (2n - k) .

Wenn keine der ersten n Ziehungen erfolgreich war, befinden sich 2n - k Socken auf dem Stapel und alle würden zu einem passenden Paar führen. Daher ist die Erfolgswahrscheinlichkeit n / (2n - n) = 1 .

Wie es funktioniert

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

Gelee, 8 Bytes

Rx2ẊĠṪ€Ṃ

Probieren Sie es 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

Zur Verifizierung finden Sie hier eine Version , die sowohl die gewünschte Ausgabe als auch das Ergebnis der "Zufallslisten" -Operation anzeigt (um zu sehen, in welcher Reihenfolge Socken gezeichnet wurden).

Python, 66 Bytes

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

Dennis hat sich eine clevere Möglichkeit ausgedacht, die Dinge neu zu ordnen und dabei 5 Bytes zu sparen.

MATL , 16 15 Bytes

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

Probieren Sie es online! Oder beobachten Sie die empirische Verteilung für 1000 Proben im Fall N = 7 (es dauert eine Weile).

Dies erzeugt direkt die Zufallsvariable, die das Ergebnis darstellt, basierend auf seiner Wahrscheinlichkeitsverteilung. Lassen N die Anzahl der Sockenpaare, und sei p ( k die Wahrscheinlichkeit) bezeichnen , dass die k -te Unentschieden erfolgreich ist, konditioniert auf die Tatsache , dass die k -1-ten Unentschieden nicht erfolgreich war. Dann (siehe auch hier ):

• p (1) ist offensichtlich 0. Sie können kein Paar mit einer einzelnen Socke haben.
• p (2) ist 1 / (2 · N - 1). Bei der zweiten Ziehung gibt es eine Gewinnsocke, die aus 2 * N −1 verbleibenden Socken ausgewählt werden kann.
• p (3) ist 2 / (2 · N - 2 ). Bei der dritten Ziehung gibt es 2 Gewinnsocken aus 2 * N −2. Die Anzahl der Gewinnsocken beträgt 2, da die beiden Socken, die Sie nach dem zweiten Draw erhalten haben, unterschiedlich waren.
• Nach der gleichen Überlegung ist p ( k ) im Allgemeinen ( k - 1) / (2 * N - k + 1).
• Nach der obigen Formel ist p ( N + 1 ) 1. Wenn Sie die N + 1-te Ziehung erreichen, ist Ihr Erfolg garantiert.

Der Code iteriert also für maximal N + 1 Zeichen. Bei der k- ten Ziehung wird eine Zufallsvariable erzeugt, die gleich 1 mit der Wahrscheinlichkeit ( k - 1) / (2 · N - k ) ist, oder anders 0. Immer wenn die Zufallsvariable gleich 1 ist (die Ziehung war erfolgreich), stoppt der Prozess und der Strom k wird ausgegeben.

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 Bytes

EZ@G\&=XRafX<

Probieren Sie es online! Oder beobachten Sie die empirische Verteilung für 4000 Proben im Fall N = 7 (es dauert eine Weile).

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 Bytes

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

Erläuterung

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 Bytes

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

Teste es hier.

Python 3, 142 105 104 Bytes

Vielen Dank an Eʀɪᴋ ʀɪᴋ Gᴏʟғᴇʀ für das Speichern eines Bytes!

Meine erste Antwort:

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

Meine neue Antwort:

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

Beide beenden mit einem NameErroron s.

R 49

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

Ich bin mir sicher, dass es einen besseren Weg dafür in R geben muss! Ich habe versucht, etwas schlaueres zu machen, aber es hat nicht funktioniert.

Edit: Verbessert von @bouncyball, da es keine Funktion sein muss.

Python 2, 101 Bytes

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

VBA, 61 Bytes

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

- modelliert die Verschiebungswahrscheinlichkeit der Sockenübereinstimmung bei vorheriger Nichtübereinstimmung. Bei der Bewertung ist K "Socken in der Hand", also ist die Ziehungszahl eins mehr.

Pyth, 14 Bytes

lhfnT{T._.S*2S

Erläuterung:

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