todos por igual

Published 16/10/2007 15:30

Este es otro problema de algoritmia generica, antes de que sigamos analizando algoritmos y tecnicas de diseño, para intentar pensar "out-of-the-box".

Imaginemos que tenemos un array de enteros, de tamaño K, y un flujo del que vamos leyendo enteros, hasta un numero N. No conocemos N de antemano, pero sabemos que sera igual o mayor que K. Lo que queremos es tener en nuestro array de K posiciones una muestra equiprobable de los enteros del flujo.

¿Que quiere decir esto? Imaginemos que nuestro array tiene K=5 elementos y supongamos una notacion (a-b-c) para un flujo que contenga los elementos a, b y c.

Si nuestro flujo fuera todo de unos, como en (1-1-1-1-1-1-1), nuestro array final debe contener 5 unos siempre.

Si en cambio nuestro flujo fuera algo como (1-1-1-1-2-1-1-1-1-2), debe haber 4 veces mas posibilidades de tener unos que doses, con lo que nuestros posibles resultados serian: un array con todo unos (aproximadamente un 22.2% de las veces), un array con 4 unos y 1 dos (el dos puede estar en distintas posiciones, pero ocurrira aproximadamente un 55.6% de las veces) y un array con 3 unos y 2 doses (de nuevo pudiendo estar los doses en distintas posiciones, y que ocurrira aproximadamente el 22.2% de las veces)


Supongamos que nuestro flujo de entrada esta modelado mediante las funciones:

- boolean hasNext(): devuelve true si quedan elementos por leer, false en otro caso
- int getNext(): obtiene el siguiente entero del flujo mientras queden elementos, o un valor indeterminado en otro caso

Dado un numero K de posiciones para el array, y un flujo de entrada de longitud N indeterminada (pero finita): ¿serias capaz de construir el algoritmo para devolver una muestra equiprobable tal como la hemos definido anteriormente?

nota: las funciones que modelan el flujo estan dadas en notacion estilo C. Podeis cambiarlas a algo apropiado en el lenguaje que utiliceis, siempre y cuando conserven la semantica, claro 

por phobeo
Archivado en: ,
Comparte este post:

Comentarios

# Lucas Ontivero said on Wednesday, October 17, 2007 2:16 AM

Dejame que te cuente lo que le pasó a Capablanca, un campeón mundial de ajedrez,  que a mi entender fue el más increible de todos los tiempos.

A él le encantaba resolver problemas y los resolvía increiblemente rápido. Hasta que un buen dia se decidió y creo un problema, se los presentó a sus colegas "los grandes maestros" pero después de muuuuchas horas de analizarlo ninguno de los grandes maestros lo habia resuelto y el tiempo pasó y pasó y seguian viendolo y planteando algunas ideas pero nada, no lo resolvian. Capablanca se indignó y les mostró la solución, "Ven es así y así y después el rey tiene que ir acá o acá a lo que movemos esto acá y..." y siguió mostrandolo. Claro, era larguísimo y dificilísimo pero Capa se frustró y nunca más volvió a crear otro problema. Para qué voy a hacer problemas que nadie puede resolver?

Pero vos no sos capablanca y yo me voy a poner con esta creación tuya solo que esta vez tendré más cuidado de no tirar la primera solución que se me ocurra :)

Saludos!

# phobeo said on Wednesday, October 17, 2007 2:14 PM

buenas Lucas,

reconozco que en este se me ha ido un poco la mano... pero de ahi a lo de Capablanca, hay un trecho! Y en cualquiera de los casos, pienso seguir mandando problemas (de distintos niveles) todas las semanas mientras vosotros querais hacerlos! };D

Dejo una pista por si alguien se atasca un poco:

(para de leer aqui si no quieres usar pistas!)

pista: Hay veces que resolvemos problemas de proceso de datos organizandolos en una estructura adecuada, contando, creando porcentajes, etc... segun sea preciso (y puede funcionar, de hecho). Pero tambien hay veces en las que todo eso no es necesario. Piensa "out-of-the-box"! }:)

# Serabe said on Wednesday, October 17, 2007 6:23 PM

Lo más cercano a lo que he llegado es lo siguiente:

Por una parte, sea n el número de datos hasta el momento. Por otro, sea a el array con todos los números. Cuando nos dan el primer número x_1 rellenamos todo a con x_1. Según nos van llegando números, vamos recalculando a partir de n y de a el porcentaje de cada número y rehaciendo el array. Problema, costoso y que, por ejemplo, en una fila de f(a.size,n) unos (f siendo una función que hace que a.size unos del array valgan bastante) y después todo 3, por ejemplo, devolvería un array de todo unos, por muy grande que fuese la cadena de treses. No sé si me he explicado. La cadena en cuestión sería:

11111111111111111111111111111...111111133333........

Después pensé en que, dado m' tamaño de a y m = m' si m' es par o m=m'-1 si m' es impar, almacenar m/2 pares de valor veces que ha salido. El problema sigue siendo el mismo, sólo que la cadena tendría que ser:

1111...111222....222333...(m/2)(m/2 + 1)...

Por supuesto, al final, a partir de los datos, se crearía el array.

De momento, ¿qué tal voy?

# Tio_Luiso said on Thursday, October 18, 2007 2:58 PM

Tal y como yo lo veo: Si N fuera (que no es) un array y permitiera acceso aleatorio, el problema sería sencillísimo. Cualquier subcadena de tamaño K de N satisfaría la solución. También la satisfaría cualquier colección de caracteres aleatorios de N.

Pero no es un array.

Las operaciones que se pueden realizar sobre N recuerdan a un IEnumerator, con una propiedad Current para acceder al elemento actual, un método MoveNext para obtener el siguiente elemento, y un método Reset (que no existe en N) para posicionar el cursor al principio del IEnumerator (de hecho, antes del 1er elemento).

Si fuera así, podría usar un Random para obtener un entero aleatorio a cada paso, que me daría el número de posiciones a avanzar. Como N es finito, eventualmente podríamos llegar a salirnos por el final. Pero si tenemos un método Reset, podríamos continuar desde el principio.

Pero no lo tenemos.

Entonces se me ocurre que podríamos hacer esto que acabo de decir, almacenando los items leidos en alguna estructura a modo de buffer, de tal forma que si en algún momento llegáramos a sobrepasar el final, el resto de los elementos que tuviéramos que seleccionar, los podríamos seleccionar de esta estructura. No es lo más elegante, pero es razonablemente sencillo.

¿Te intento escribir un cacho de código?

# Tio_Luiso said on Thursday, October 18, 2007 3:17 PM

Me contesto yo solo:

Basándome en lo que he propuesto, para que la muestra tomada fuera realmente equiprobable, el generador de enteros aleatorios tendría que devolver idealmente un entero aleatorio entre 1 y el tamaño de N. Si fuera menor, creo que la muestra no sería equiprobable. Y si fuera mayor, creo que tampoco.

¿Me equivoco mucho?

Siempre nos queda la solución cutre: Nos volcamos todo N en una estructura de acceso aleatorio, con lo cual, ya tendríamos 2 cosas: 1.- poder acceder al elemento que queramos y 2.- Conocer el tamaño de N.

# suge said on Thursday, October 18, 2007 3:59 PM

Hola. Soy nuevo en esto y no se si tendría que ponerlo en pseudocodigo o no. Lo pongo en literatura y si hace falta lo codifico cuando tenga un rato. Como lo veo sería algo así :

Vamos rellenando una lista de duplas, con los valores que van saliendo y su número de apariciones. Supongamos que nos queda una lista como la siguiente:

Valores  Apariciones

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

3                              5

12                           1

6                              4

7                              3

1                              1

Una vez terminada la lista (terminada la lectura de los k valores), la recorremos  cambiando el valor apariciones por la suma de las anteriores -1 (esto último es por cómo hacemos luego el sorteo). Tendríamos algo como

Valores ExtremoSup

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

3                     4

12                   5

6                     9

7                    12

1                    13

Cuando estamos en este punto ya solo nos queda hacer un “sorteo” con N valores “premiados. Es decir un bucle for de 0 a N-1 con un randomize que nos de valores enteros entre 0 y K-1,   y cada valor aleatorio se compara con los llamados Extremos superiores de la lista por orden ; si es menor o igual que el valor con que se compara ya tenemos el elemento equi-probable para la posición N del array solución, si no comparamos con el siguiente.

# phobeo said on Thursday, October 18, 2007 7:49 PM

buenas! perdon por el retraso en responder, llevo ayer y hoy de viajes y sin conexion!

serabe: tu primera idea ya has visto que no funcionaria porque no respeta lo que comentabamos de la equiprobabilidad. Tu segunda aproximacion entiendo que es coleccionar los pares de (valor - numero de apariciones) de forma similar a como sugiere despues suge (ver comentario mas abajo) pero lo que no me queda claro es que harias luego con ellos, ni por que solo guardas m/2 valores. Puedes dar mas detalles?

Tio_Luiso: jejeje... como siempre muy avispado! Efectivamente, si tuvieramos un array o un metodo Reset() para volver atras, seria mucho mas facil... pero no los tenemos... aunque los comentarios que dejas son muy buenos como "pista" };D

Como comentas justo despues... si lo volcamos todo a una lista, tendriamos la posibilidad de hacer lo que dijiste en el primer comentario pero... la cuestion es: hace falta? Dejo una pista debajo del comentario, por si quieres leerla

suge: Bienvenido! Si, aceptamos pseudocodigo, C#, Java, Ruby... incluso Visual Basic! La mayoria de problemas son mas para "investigar" algo que para explicar "caracteristicas" de lenguajes... aunque tambien dejaremos caer alguno mas especifico }:)

En cuanto a tu solucion: efectivamente, podria funcionar, pero necesitaria una pequeña modificacion: Imagina el caso del flujo que mencionabamos que tenia un dos por cada cuatro unos. En este caso, tu estructura de sorteo quedaria como:

valor: 1 extremo: 7

valor: 2 extremo: 9

Peeeeero que pasaria si las 5 veces nuestra funcion aleatoria devuelve un 8? (puede pasar, es una funcion aleatoria) No existe niguna posibilidad de que una muestra tenga mas instancias de un elemento (doses, en este caso) que las que tenemos en el flujo.

A mi se me ocurren dos formas de modificar tu algoritmo para que funcione correctamente. Si te animas a buscarlas, podrias intentar despues buscar otra solucion "sin almacenar tantos datos" };)

Y por ultimo, como dije antes, voy a dejar otra pista por si alguien de los que "casi" lo tiene se anima a dar una solucion aun mas optima... no leais si quereis hacerlo sin pistas!

pista:

Con los comentarios que han dado, podeis dar una solucion que usa memoria constante, no importa lo grande que sea N

# Tio_Luiso said on Friday, October 19, 2007 10:20 AM

Me parece (seguramente me equivoco) que a menos que conozca el tamaño de N, la muestra que tome no será equiprobable. Al menos siguiendo mi aproximación.

Si conozco el tamaño de N, podría tomar K enteros aleatorios desde 0 hasta el tamaño de N menos uno (sin repetición), y obtener los K elementos de N con un solo recorrido.

Si no conozco el tamaño de N, puedo acotar N diciendo que es como poco igual de grande que K y obtener los K elementos de este subconjunto de N. Pero estaríamos despreciando los elementos del resto de N, y por lo tanto, la muestra no sería equiprobable. De hecho, ocurrirá lo mismo con cualquier límite arbitrario que establezca para los números aleatorios, a menos que este límite sea exactamente el tamaño de N, en cuyo caso, los números aleatorios que obtengamos serán elementos equiprobablemente aleatorios de N. ¿No?

Obviamente me estoy confundiendo en algún punto.

# suge. said on Friday, October 19, 2007 12:54 PM

Gracias por la bienvenida. Y lo siento por la cagada :-). Mira que no tener en cuenta el que un numero pudiera aparecer en la salida un número de veces mayor que el número de veces que aparece en la entrada !!!.

Grácias por la atención. Creo que tendré que revisar los planteamientos porque si lo mantengo más o menos igual y repito el sorteo en caso de que el valor que salga haya alcanzado su numero máximo de apariciones , y haciendo una traza sencilla, veo que no cumplo la equiprobabilidad. Lo pienso mejor.

De todas formas e tenido intuición (digo intuición por que ahora me faltan matematicas para poder comprobarlo), y solo lo he probado haciendome una traza a mano y parece que no va mal. A ver que te parece:

Leemos el primer elemento y lo metemos en la primera posición del array, leemos el segundo y a la segunda y así hasta llenarlo (los k primeros). Una vez que lo tenemos ahí leemos el siguiente k+1. Calculamos un entero aleatorio(lo llamo j) entre 1 (supongo arrays con posición inicial 1) y k+1 ; si es menor o igual  que k (j<=k) colocamos el elemento en la posición j del array , si no seguimos con el siguiente elemento .Calculamos un aleatorio entre 1 y k+2; si es menor que k a la posición correspondiente del array , si no seguimos con el siguiente, …. Y  así hasta el elemento N.

¿Qué tal suena?.

# Serabe said on Friday, October 19, 2007 1:38 PM

Para resolver tu duda necesito hacer una pregunta... ¿puedo tener más variables a parte del n y del array?

# phobeo said on Saturday, October 20, 2007 1:58 PM

suge: Hey! De sentirlo nada! Lo importante es ir proponiendo soluciones y ver como se ajustan o no (estamos aqui para "formarnos mentalmente" y no tanto para "dar con la solucion correcta", eso lo dejamos para el trabajo };D)

Como ya comente, creo que puedes cambiar la solucion que proponias... aunque claro, requiere ir haciendo recorridos para actualizar los valores de tu tabla cada vez. Sin embargo, la solucion que acabas de proponer parece mas sencilla... y usa memoria constante (solo necesita un contador y el generador de numeros aleatorios)... a mi me gusta! }:)

Te animas a mandar codigo para esa solucion? }:)

serabe: Si, puedes usar mas memoria, of course. Pero como ya deje caer antes (y ya alguien se dio cuenta)... puede hacerse con muy poquita memoria extra! };)

# suge said on Monday, October 22, 2007 10:05 AM

Ahí va en C#. Quedaría algo más o menos así:

public static int[] arrayEquiprobable(myStream flujo_de_entrada, int long_array)

       {

           int posicionEstudiada = 0;

           int[] array_solucion = new int[long_array];

           Random miRandom =new Random(DateTime.Now.Millisecond);

           int posAleatoria ;

           while(flujo_de_entrada.hasNext())

           {

               if (posicionEstudiada<long_array)

               {

                   array_solucion[posicionEstudiada]=flujo_de_entrada.getNext();  

               }

               else

               {

                   posAleatoria=miRandom.Next(posicionEstudiada);

                   if (posAleatoria<long_array)

                       array_solucion[posicionEstudiada]=flujo_de_entrada.getNext();  

                   else

                       flujo_de_entrada.getNext();  

               }

               posicionEstudiada++;

           }

           if (posicionEstudiada < long_array)

           {

               throw (new Exception("La longitud propuesta de la solución es" +

                           "mayor que el tamaño del stream.Situación no valida"));

           }

           return array_solucion;

       }

Lo he dejado sin comentarios pero creo que se sigue bien.

SaludOs.

# Tio_Luiso said on Monday, October 22, 2007 3:39 PM

Ya he visto mi error. Lo que propone suge (a falta de revisar el código, cosa que no he hecho) me parece que está bien.

He hecho unos calculillos para ver si pa probabilidad de aparición de cada elemento en la muestra es la misma (la definición de equiprobabilidad), y lo es. He calculado la probabilidad que tiene cualquier elemento de entrar "inicialmente" en el array, y la probabilidad que tiene cualquier elemento posterior de entrar pisándolo (condicionado a que haya entrado previamente el elemento en el que estamos interesados). La resta de estas dos probabilidades tiene que ser una constante para todos los elementos. De hecho, tiene que acabar siendo igual a TamK / TamN para todos los elementos de N.

Si no hace falta que haga aquí los cálculos, mejor.

# phobeo said on Monday, October 22, 2007 7:36 PM

suge: Efectivamente, es una solucion! }:)

Sin embargo, yo lo refactorizaria un poco para que las condiciones "similares" (por ejemplo: cuando insertamos en el array) se hagan en el mismo bloque de codigo. Suele ser buena idea cuando hay multiples posibilidades de ejecutar la misma accion en un trozo de codigo por si en el futuro añades/eliminas condiciones y lo hace mas legible

Tio_Luiso: Efectivamente, la solucion de suge se ajusta a lo que comentabamos... y no, no hace falta que hagas los calculos en un comment! }:)