[Programación] Fwd: Re: [Programación] Re: [Programación] Fwd: Re: [Programación] Re: [Programación] agrupar cartones de bingo

[Federico Wiecko]

On Monday 14 March 2005 19:32, Horacio Castellini wrote:
> > No Horacio, es obvio por el enunciado del problema
> > que el orden en que
> > aparecen los números es irrelevante.
> >
> > Yo buscaria solucionarlo mediante funciones
> > recursivas por medio de algún
> > lenguaje funcional. Si tengo tiempo, esta semana te
> > mando una solución en
> > Haskell.
>
> Si es relevante... no es lo mismo generar 15504
> cartones que 19!=1.22*10^17 cartones... en este último
> caso deja de ser un problema P y pasa a ser NP y aca
> la limitación es la máquina de Turing...
> independientemente del lenguaje que uses...

Claro, tenés razón sin duda.... por algún motivo pense (de memoria en
realidad :-P) que el orden era irrelevante .. pero en el problema esto no se
aclara.
La pregunta fundamental, como bien formula Horacio es :
los cartones  [1,2,3,4,5]  y  [5,4,3,2,1]   son iguales ???

Otra cosa:
una agrupacion posible es:

[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20]   (1)

y otra es
[2,3,4,5,6],[1,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20]   (2)

lo que demuestra que un mismo cartón podría estar en distintas agrupaciones de
a 4.

La pregunta es cuantos posibles cartones tenemos en este caso ?

Supongamos que el orden de los numeros es irrelevante (o sea 
[1,2,3,4,5]=[5,4,3,2,1])

Tomamos 1 de los 15504 cartones, para el segundo cartón tenemos C(15,5), para
el tercero C(10,5) mientras que el cuarto es indefectiblemente uno solo.

Por lo tanto la cantidad de planchas con 4 cartones deben ser:

15504 * C(15,5) * C(10,5) * 1  = 11 732 745 024   (según la calculadora de
google)

Ahora bien, como los cartones no pueden estar repetidos en la solución
entonces vamos a tener ahora 15504 / 4 = 3876  pero no va a existir solución
única  (podría usar el cartón [11,12,13,14,15] como en (1) o como en (2)).

Federico .-

> Por otro lado toda función recursiva tiene su
> equivalente en función iterativa (pero no alverre)...
>
>
>
>
>
>
>
>
> ___________________________________________________________
> 250MB gratis, Antivirus y Antispam
> Correo Yahoo!, el mejor correo web del mundo
> http://correo.yahoo.com.ar
> _______________________________________________
> Programacion mailing list
> Programacion@lugro.org.ar
> http://www.lugro.org.ar/mailman/listinfo/programacion

-------------------------------------------------------