Antecedentes

Tengo una colección de "calcetines entre semana", que son siete pares de calcetines etiquetados por los días de la semana. Cuando lavo mis calcetines, terminan en una pila, y debo organizarlos en los pares correctos antes de ponerlos en el armario. Mi estrategia es sacar un calcetín al azar de la pila a la vez y ponerlo en un cajón. Cada vez que hay un par de calcetines a juego en el cajón, los ato y los guardo en el armario. Su tarea es simular este proceso aleatorio y devolver el número de sorteos necesarios para encontrar el primer par coincidente.

Entrada

Su entrada es un entero N ≥ 1 . Representa el "número de días en una semana": hay N pares de calcetines en la pila, y cada par tiene una etiqueta distinta. Si es necesario, también puede tomar una semilla PRNG como entrada.

Salida

Su salida es la cantidad de calcetines que tengo que dibujar antes de encontrar el primer par coincidente. Por ejemplo, si los dos primeros calcetines ya forman un par coincidente, la salida es 2.

Por supuesto, la salida es aleatoria y depende del orden de dibujo. Suponemos que todas las órdenes de dibujo son igualmente probables , de modo que cada vez que se dibuja un calcetín, la elección es uniforme e independiente de todas las demás opciones.

Ejemplo

Deje N = 3 , para que tengamos 6 calcetines en total, etiquetados como AABBCC . Una posible ejecución del "protocolo de dibujo de calcetines" es la siguiente:

       | 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

El primer par coincidente se encontró después de dibujar el segundo B , que fue el tercer calcetín que se dibujó, por lo que la salida correcta es 3.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten. La entrada y la salida pueden estar en cualquier formato razonable, incluido unario (cadena de 1s).

Puede suponer que el RNG incorporado en su idioma es perfecto. No tiene que simular realmente el protocolo de dibujo de calcetines, siempre que sus salidas tengan la distribución de probabilidad correcta.

"Casos de prueba"

Estas son las probabilidades aproximadas de todas las salidas para la entrada 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

Para probar su solución, puede ejecutarla, por ejemplo, 40 000 veces y ver si la distribución de salida está razonablemente cerca de esto.

Jalea , 8 bytes

ḤX€Ṛ<RTḢ

Pruébalo en línea! o verificar la distribución para N = 7 .

Antecedentes

Sea n el número de pares; Hay 2n calcetines individuales.

Para el primer sorteo, hay 2n calcetines y 0 de ellos darían como resultado un par coincidente. Por lo tanto, la probabilidad de éxito es 0 / 2n = 0 .

Como el primer sorteo no fue exitoso, hay 2n - 1 calcetines en la pila y 1 de ellos resultaría en un par coincidente. Por lo tanto, la probabilidad de éxito es 1 / (2n - 1) .

Si el segundo sorteo no tuvo éxito, hay 2n - 2 calcetines en la pila y 2 de ellos darían como resultado un par coincidente. Por lo tanto, la probabilidad de éxito es 2 / (2n - 2) .

En general, si los primeros k sorteos no tuvieron éxito, hay 2n - k calcetines en la pila y 2 de ellos darían como resultado un par coincidente. Por lo tanto, la probabilidad de éxito es k / (2n - k) .

Finalmente, si ninguno de los primeros n sorteos fue exitoso, hay 2n - k calcetines en la pila y todos darían como resultado un par coincidente. Por lo tanto, la probabilidad de éxito es n / (2n - n) = 1 .

Cómo funciona

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

Jalea, 8 bytes

Rx2ẊĠṪ€Ṃ

Pruébalo en línea!

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

Para verificar, aquí hay una versión que muestra tanto el resultado deseado como el resultado de la operación de "lista aleatoria" (para ver en qué orden se dibujaron los calcetines).

Python, 66 bytes

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

Dennis pensó en una forma inteligente de reorganizar las cosas, ahorrando 5 bytes.

MATL , 16 15 bytes

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

Pruébalo en línea! O observe la distribución empírica para 1000 muestras en el caso N = 7 (lleva un tiempo).

Esto genera directamente la variable aleatoria que representa el resultado, en función de su distribución de probabilidad. Sea N el número de pares de calcetines, y sea que p ( k ) denote la probabilidad de que el k -ésimo sorteo sea exitoso, condicionado al hecho de que el k -ésimo sorteo no fue exitoso. Entonces (ver también aquí ):

• p (1) es obviamente 0. No puedes tener un par con un solo calcetín.
• p (2) es 1 / (2 * N −1). En el segundo sorteo hay un calcetín ganador que se puede elegir entre 2 * N −1 calcetines restantes.
• p (3) es 2 / (2 * N −2). En el tercer sorteo hay 2 calcetines ganadores de 2 * N −2. El número de calcetines ganadores es 2 porque los dos que obtuviste después del segundo sorteo fueron diferentes.
• En general, por el mismo razonamiento, p ( k ) es ( k −1) / (2 * N - k +1)
• Por la fórmula anterior, p ( N +1) es 1. Si llegas a la N sorteo + 1-th, tienes la garantía de tener éxito.

Entonces el código itera para un máximo de N +1 sorteos. En el sorteo k se genera una variable aleatoria que equivale a 1 con probabilidad ( k -1) / (2 * N - k ), o 0 en caso contrario. Siempre que la variable aleatoria sea igual a 1 (el sorteo ha sido exitoso), el proceso se detiene y se genera la k actual .

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<

Pruébalo en línea! O observe la distribución empírica para 4000 muestras en el caso N = 7 (lleva un tiempo).

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}

Explicación

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(&}#)

Pruébalo aquí.

Python 3, 142 105 104 bytes

¡Gracias a Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ por guardar un byte!

Mi primera respuesta

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

Mi nueva respuesta:

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

Ambos salen con un NameErrorencendido s.

R, 49

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

¡Estoy seguro de que debe haber una mejor manera de hacer esto en R! Intenté hacer algo más inteligente pero no funcionó.

Editar: Mejorado por @bouncyball ya que no tiene que ser una función.

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

- modela la probabilidad de cambio de calcetín dada la falla previa de coincidencia. En el punto de evaluación, K es "calcetines en la mano", por lo que el número de sorteo es uno más.

Pyth, 14 bytes

lhfnT{T._.S*2S

Explicación:

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