Contar sin enumerar

Toda pregunta de conteo es en realidad una pregunta sobre cuántas respuestas tiene un procedimiento de decisión. Ya conoces una forma de responder a esas preguntas: escribir un bucle, enumerar, mirar la salida. Funciona mientras la salida es pequeña, y entonces deja de funcionar por completo, no poco a poco. Esta lección trata de obtener el número sin llegar a producir nunca la lista.

/* multiplication rule */

  3 starters * 4 mains * 2 desserts  =  24

  plate: 4 letters, 3 digits
  26^4          = 456976
  26^4 * 10^3   = 456976000

  /* addition rule */
  12 routes + 7 routes  =  19 routes

La regla del producto es el fundamento, y es de verdad así de simple: si una primera elección puede hacerse de a formas y, después de ella, una segunda de b formas, el par puede hacerse de a por b formas. Dos reglas prácticas la mantienen honesta. Multiplica cuando las elecciones ocurren en secuencia; suma cuando son alternativas que nunca se dan juntas. Casi todos los errores de conteo son una de estas dos reglas usada donde correspondía la otra.

/* ordered choice: pile of 10 people, 3 different prizes */

10 choices, then 9, then 8

  P(10, 3)  =  10 * 9 * 8
            =  720

  P(n, r)   =  n! / (n - r)!

Diez personas y tres medallas distintas dan setecientas veinte formas, y la regla del producto sola te lleva hasta ahí: diez opciones para el oro, nueve restantes para la plata, ocho para el bronce. Es una selección ordenada, que se escribe P de n y r, y la fórmula es un producto decreciente que se corta tras r factores, es decir n factorial dividido entre n menos r factorial. El número solo es grande porque el orden cuenta como información.

/* unordered choice: same 10 people, 3 identical seats */

  C(n, r)   =  P(n, r) / r!

  C(10, 3)  =  720 / (3 * 2 * 1)
            =  720 / 6
            =  120

Ahora quitamos el orden. Las mismas tres personas en otro orden sobre el podio no son un resultado distinto cuando los premios son iguales, son un grupo. Cada grupo de tres se contó tres factorial veces, una por cada orden, así que dividir entre tres factorial corrige exactamente ese recuento de más. Ese es todo el motivo de que el divisor sea r factorial y no otra corrección: es el número de órdenes que acabas de decidir que no te importan. C de 10 y 3 es 120, seis veces menor que la respuesta ordenada, y la regla para recordar es que las combinaciones son permutaciones con el orden dividido fuera.

El principio del palomar es el primer argumento de conteo que da una respuesta garantizada en lugar de una probable. Si n objetos se reparten en m cajas y n es mayor que m, alguna caja contiene al menos dos. Eso es todo lo que dice, es obvio, y sin embargo es una de las herramientas más útiles del análisis de algoritmos, porque produce certeza a partir de puro conteo. Una aplicación real: una tabla hash tiene más claves posibles que cubos, así que las colisiones no son señal de una mala función hash, son una certeza matemática. Lo que hace una buena función hash es repartirlas de manera uniforme, no eliminarlas. Cualquier argumento de que tu sistema no verá colisiones porque el hash es bueno está equivocado antes de empezar.

El principio del palomar explica también por qué la pregunta de cuántas personas hacen falta para que dos compartan cumpleaños no es la que todo el mundo responde primero. La gente compara el número de personas con el número de días y dice ciento ochenta. Pero las cajas no son personas contra días, son parejas de personas contra días, y el número de parejas crece de forma cuadrática mientras el número de personas crece de forma lineal. Con veintitrés personas hay doscientas cincuenta y tres parejas y la probabilidad de al menos una coincidencia ya ronda la mitad. Es la misma forma que el argumento de colisiones de arriba, y es la razón de que un identificador aleatorio de sesenta y cuatro bits esté bien mientras que uno de dieciséis bits es un incidente en producción.

birthday problem, 365 days

  two people differ:  364 / 365

  23 people:

  C(23, 2)  =  23 * 22 / 2  =  253 pairs

  (364 / 365)^253  =  0.4995
  1 - 0.4995       =  0.5005

  70 people:  1 - (364 / 365)^2415  >  0.999

Lee los números del cumpleaños como una advertencia sobre la intuición, no como un truco de fiesta. Sesenta personas producen mil setecientas setenta parejas, y la probabilidad de un cumpleaños compartido pasa del noventa y nueve por ciento. Ahí no hay nada sutil aritméticamente; la sorpresa viene entera de que estimamos los sucesos por parejas como si fueran independientes, y no lo son. La versión práctica para quien programa es que el espacio de colisiones es cuadrático en el número de objetos, así que la cota del cumpleaños siempre es mucho más baja que la ingenua.

/* brute force, 10^9 steps per second */

n = 1    2!        =  2
n = 10   10!       =  3.6 * 10^6
n = 13   13!       =  6.2 * 10^9    6 seconds
n = 15   15!       =  1.3 * 10^12   22 minutes
n = 18   18!       =  6.4 * 10^15   74 days
n = 20   20!       =  2.4 * 10^18   77 years
n = 25   25!       =  1.6 * 10^25   5 * 10^8 years

Y por último, por esto importa contar para los algoritmos. Una búsqueda por permutaciones sobre veinte elementos no es veinte veces más lenta que sobre un elemento, es veinte factorial, lo que supera con holgura el número de segundos que el universo lleva existiendo. Los saltos entre las líneas de abajo no son una curva suave, son un precipicio, y ese precipicio es la razón de que un algoritmo correcto con entradas pequeñas pueda ser completamente inútil con las reales. Cuando alguien dice que un problema es difícil, normalmente quiere decir que la solución por fuerza bruta es un número de permutaciones, y ninguna cantidad de hardware cambia eso.