Simulate a sock drawer

Question

Background

I have a collection of "weekday socks", which are seven pairs of socks labeled by the days of the week. When I wash my socks, they end up in a pile, and I must arrange them into the correct pairs before putting them into the closet. My strategy is to pull one random sock from the pile at a time and put it on a drawer. Whenever there's a matching pair of socks on the drawer, I tie them together and put them in the closet. Your task is to simulate this random process and return the number of draws required to find the first matching pair.

Input

Your input is an integer N ≥ 1. It represents the "number of days in a week": there are N pairs of socks in the pile, and each pair has a distinct label. If necessary, you may also take a PRNG seed as input.

Output

Your output is the number of socks I have to draw before the first matching pair is found. For example, if the first two socks already form a matching pair, the output is 2.

Of course, the output is random, and depends on the drawing order. We assume that all drawing orders are equally likely, so that each time a sock is drawn, the choice is uniform and independent from all other choices.

Example

Let N = 3, so that we have 6 socks in total, labeled A A B B C C. One possible run of the "sock-drawing protocol" is as follows:

       | 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

The first matching pair was found after drawing the second B, which was the third sock to be drawn, so the correct output is 3.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Input and output can be in any reasonable format, including unary (string of 1s).

You may assume that your language's built-in RNG is perfect. You don't have to actually simulate the sock-drawing protocol, as long as your outputs have the correct probability distribution.

"Test cases"

Here are the approximate probabilities of all outputs for the 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

To test your solution, you can run it for, say, 40 000 times and see whether the output distribution is reasonably close to this.

Answer 1

Jelly, 8 bytes

ḤX€Ṛ<RTḢ

Try it online! or verify the distribution for N = 7.

Background

Let n be the number of pairs; there are 2n individual socks.

For the first draw, there are 2n socks and 0 of them would result in a matching pair. Therefore, the probability of success is 0 / 2n = 0.

Since the first draw wasn't successful, there are 2n - 1 socks on the pile and 1 of them would result in a matching pair. Therefore, the probability of success is 1 / (2n - 1).

If the second draw wasn't successful, there are 2n - 2 socks on the pile and 2 of them would result in a matching pair. Therefore, the probability of success is 2 / (2n - 2).

In general, if the first k draws were unsuccessful, there are 2n - k socks on the pile and 2 of them would result in a matching pair. Therefore, the probability of success is k / (2n - k).

Finally, if none of the first n draws was successful, there are 2n - k socks on the pile and all of them would result in a matching pair. Therefore, the probability of success is n / (2n - n) = 1.

How it works

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

Answer 2

Jelly, 8 bytes

Rx2ẊĠṪ€Ṃ

Try it 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

To verify, here is a version that displays both the desired output and the result of the "shuffle list" operation (to see what order socks were drawn in).

Answer 3

Python, 66 bytes

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

Dennis thought up a clever way to rearrange things, saving 5 bytes.

Answer 4

MATL, 16 15 bytes

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

Try it online! Or observe the empirical distribution for 1000 samples in the N=7 case (it takes a while).

This directly generates the random variable representing the result, based on its probability distribution. Let N be the number of sock pairs, and let p(k) denote the probability that the k-th draw is successful, conditioned on the fact that the k-1-th draw was not succesful. Then (see also here):

• p(1) is obviously 0. You can't have a pair with a single sock.
• p(2) is 1/(2*N−1). At the second draw there is one winning sock that may be chosen out of 2*N−1 remaining socks.
• p(3) is 2/(2*N−2). At the third draw there are 2 winning socks out of 2*N−2. The number of winning socks is 2 because the two socks you got after the second draw were different.
• In general, by the same reasoning, p(k) is (k−1)/(2*N−k+1)
• By the above formula, p(N+1) is 1. If you get to the N+1-th draw you are guaranteed to succeed then.

So the code iterates for a maximum of N+1 draws. At the k-th draw a random variable is generated that equals 1 with probability (k-1)/(2*N-k), or 0 otherwise. Whenever the random variable equals 1 (the draw has been succesful) the process stops and the current k is 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

Answer 5

MATL, 14 13 bytes

EZ@G\&=XRafX<

Try it online! Or observe the empirical distribution for 4000 samples in the N=7 case (it takes a while).

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

Answer 6

JavaScript, 77 73 bytes

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

Explanation

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;
};

Answer 7

CJam, 17 bytes

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

Test it here.

Answer 8

Python 3, 142 105 104 bytes

Thanks to Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ for saving one byte!

My first answer:

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

My new answer:

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

Both exit with a NameError on s.

Answer 9

R, 49

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

I'm sure there must be a better way of doing this in R! I tried doing something cleverer but it didn't work.

Edit: Improved by @bouncyball since it doesn't have to be a function.

Answer 10

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)

Answer 11

VBA, 61 bytes

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

- models the shifting probability of sock match given previous failure to match. At the point of evaluation, K is "socks in hand", so draw number is one more.

Answer 12

Pyth, 14 bytes

lhfnT{T._.S*2S

Explanation:

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