Cut the Cards

[pinkman]

Thanks for all those formulas and explanations.

Here is an implementation of the brute force algorithm for the experimental analysis:

Code:


// Forward declaration
CRDS(N);

// Main func:
// N is the number of cards
// L is the number of tests
// Returns average number of peeks
EXPORT CARDS(N,L)
BEGIN
 LOCAL I, S := 0;
 FOR I FROM 1 TO L DO
  S := S + CRDS(N); 
 END;
 RETURN S/L;
END;

// Peek a card until all cards
//   are peeked at least once
EXPORT CRDS(N)
BEGIN
 LOCAL LL, C := 0;
 LL:=MAKELIST(0,A,1,N);
 WHILE ΠLIST(LL)=0 DO
  LL(RANDINT(1,N)):=1;
  C := C+1;
 END; 
 RETURN C;
END;

Usage:
CARDS(number-of-cards, number-of-analysis)

Example:
CARDS(52, 1000)
Returns: 235.951