viernes, septiembre 03, 2004

Planteemos un pequeño juego.
Supongamos que tenemos cinco bolas numeradas del 1 al 5 metidas dentro de una caja. Saquemos las bolas una por una, al azar y vayamos apuntando los números que salen. Obtendremos algo como:

4 2 3 5 1

Observemos la secuencia y fijémonos en si hemos sacado algún número en su posición natural. Si algún número de la secuencia está en su posición natural, diremos que es una secuencia válida.
En el ejemplo, vemos que el 2 y el 3 están en sus posiciones correctas por tanto, sería una secuencia válida.
Preguntémonos, cuántas secuencias válidas existen para N elementos. Es un problema de permutaciones. Como mi combinatoria está bastante oxidada y en cambio tengo bastante reciente el Perl, he hecho un pequeño script (con la ayuda del capítulo 4 apartado 19 del O'Reilly Perl Cookbook) que realiza el cálculo.
Antes de poner el script quiero comentar que ignoraré vilmente cualquier comentario que se refiera a la eficiencia y/o diseño del programa, ya que aunque en otros tiempos me hubiesen interesado sobremanera, estoy en una fase de mi vida en la que la eficiencia me da absolutamente igual...

#!/usr/bin/perl
for($i=1;$i<=$ARGV[0];$i++){ push @d,$i;}
$oks=0;$perms=0;
permute([@d],[]);
print "-------------\n";print $oks,"/",$perms,":",$oks*100/$perms,"%\n";
sub permute { my @items = @{ $_[0] }; my @perms = @{ $_[1] }; unless (@items) { print "@perms"; $perms++; if (ok(@perms)){ print " *"; $oks++; } print "\n"; } else { my(@newitems,@newperms,$i); foreach $i (0 .. $#items) { @newitems = @items; @newperms = @perms; unshift(@newperms, splice(@newitems, $i, 1)); permute([@newitems], [@newperms]); } }}
sub ok{ $cont=1; foreach (@_) { if ($cont==$_){ return 1; } $cont++; } return 0;}

Dios mio, parece del concurso de código ofuscado. Parece que al editor de blogger no le gustan los tabuladores. Da igual...
Lo hacemos funcionar:

$ ./permuta.pl 3
3 2 1 *
2 3 1
3 1 2
1 3 2 *
2 1 3 *
1 2 3 *
-------------
4/6:66.6666666666667%

Otra vez:

$ ./permuta.pl 5
5 4 3 2 1 *
4 5 3 2 1 *
5 3 4 2 1
3 5 4 2 1

(...Ñam...)

3 2 1 4 5 *
2 3 1 4 5 *
3 1 2 4 5 *
1 3 2 4 5 *
2 1 3 4 5 *
1 2 3 4 5 *
-------------
76/120:63.3333333333333%

Si lo ejecutamos para 6, 7, 8, etc, obtendremos:

6 455/720:63.1944444444444%
7 3186/5040:63.2142857142857%
8 25487/40320:63.2118055555556%
9 229384/362880:63.2120811287478%
10 2293839/3628800:63.2120535714286%

El PC en el que lo estoy ejecutando lleva más de una hora para realizar el cálculo cuando N=15, pero parece que la serie converge en algún punto cercano al 63%

Seguramente alguno de los lectores será un gurú de la combinatoria y podrá explicarme la forma elegante de realizar este cálculo y yo se lo agradeceré regalándole una de mis cuentas en gmail ;)

Una vez visto esto. Pensemos en un caso partícular:
Cuando N=30 y en vez de bolas utilizamos muestras de ADN recogidas en un accidente aereo y una vez hecho el experimento no conseguimos una secuencia válida.
Pueden haber sucedido dos cosas:
a) Los investigadores son unos auténticos ineptos.
b) No se ha hecho ningún análisis y han tenido mala suerte, ya que la probabilidad de acertar en al menos una de las muestras estaba a su favor.

Yo me inclino por la segunda posibilidad. Y he soltado todo este rollo para tratar de olvidar las palabras de una de las viudas que contaba no saber cómo explicarle a su hijo por qué no pueden enviar otro avión para recoger a su padre...
No somos nada...