Se me presenta un reto y no se por donde cogerlo

n1x3r #1 Nov '11

Hola, estoy programando en PHP un sistema de contenidos pero tengo un problema.
Tengo diferentes contenidos, vídeo, música, y fotos por ejemplo, y necesito distribuirlo digamos en 30 partes, y se que vídeo tiene que salir 5 veces música otras 5 y fotos 20, y la cuestión es que tengo que distribuirlo de forma homogénea.

No os pido un código, sino un algoritmo para hacerlo. Para que pueda decir, en la parte 1 foto, parte 2 foto, parte 3 vídeo, parte 4 música, etc etc de forma homogénea.

Para que lo entendáis mejor

Quiero sacar esto:
$string = "foto, foto, video, foto, foto, video, musica, foto ... etc"; (cadena con los contenidos repartidos homogéneamente)

Introduciendo esto:
$foto = 20;
$video = 5;
$musica = 5;
$logitud = 30;

Os pongo otro para que lo veáis aun mas claro:

A = 2
B = 3
C = 5

La dispersión homogénea quedaría así: C-B-C-A-C-B-C-A-C-B

Igual os parece una gilipollez pero le estoy dando vueltas y no consigo dar con la tecla.

LOc0 #2 Nov '11

http://es.wikipedia.org/wiki/Regla_de_tres

Salu2

n1x3r #3 Nov '11

La solución que me aportas no puedo emplearla en este caso, esto es una dispersión, la regla de 3 es para resolver problemas de proporcionalidad, esto no tiene nada que ver.
Si sabes como aplicarlo dímelo.

Gracias de todas formas.

Un saludo.

Ulmo #4 Nov '11

¿Tiene q ser homogeneo perfecto?

Es q no se, yo lo veo una tonteria, a ver:

Tienes A=2 , B=3 y C = 5 y tienes 10 cajas donde ponerlo.

Empiezas por el elemento más alto por ejemplo, C= 5, como son 5 elementos y se tienen q distribuir homogeneamente entre 10 cajas, pues toca a 1 elemento cada 2 cajas, es decir lleno la primera caja q me encuentra vacía en los intervalos 1-2, 3-4,5-6,7-8,9-10. Es decir q lleno las cajas 1,3,5,7 y 9.

Paso al siguiente elemento B= 3, es decir 3 elementos en 10 cajas, 1-2-3, 4-5-6, 7-8-9 y nuevamente lleno en cada intervalo la primera caja q encuentre vacia, es decir: 2,4,8.

Ultimo A = 2, divide en 2 grupos 1-2-3-4-5, 6-7-8-9-10 y solo me quedan vacias las caja 3 y 10.

Ya esta, ¿no?

1 respuesta

Josepanaero #5 Nov '11

Yo lo haría también parecido a como dice #4:

Tenemos inicialmente:
A = 2
B = 3
C = 5

En primer lugar, ordenamos los grupos por tamaño de forma decreciente, es decir: C, B, A.

Además, hay que tener un vector auxiliar con las cajas libres, es decir:
aux[0] = 1
aux[1] = 2
aux[2] = 3
aux[3] = 4
aux[4] = 5
aux[5] = 6
aux[6] = 7
aux[7] = 8
aux[8] = 9
aux[9] = 10

Y la operación que hay que hacer, para cada uno de los grupos (C, B y A) es:
redondeo(tamaño_aux / tamaño_grupo)

Es decir, primero, para C, haríamos:
redondeo(10.0 / 5.0) = 2

Por lo que asignamos un C cada dos cajas, es decir, en las cajas 1, 3, 5, 7 y 9 (correspondientes a las posiciones 0, 2, 4, 6 y 8 del vector auxiliar). Además, eliminamos esos elementos del vector auxiliar, quedando así:
aux[0] = 2
aux[1] = 4
aux[2] = 6
aux[3] = 8
aux[4] = 10

Luego hacemos lo mismo para B:
redondeo(5.0 / 3.0) = redondeo(1.6666) = 2

Por lo que metemos un B cada 2 posiciones, es decir, en la posición 0, 2 y 4 del vector auxiliar (correspondientes a las cajas 2, 6 y 10, respectivamente). Tras eliminar estos elementos del vector auxiliar, tendríamos:
aux[0] = 4
aux[1] = 8

Y hacemos el mismo procedimiento para A (esto ya es trivial).

Seguramente haya otras implementaciones más eficientes, pero ésta es la primera que se me ha venido a la cabeza y creo que funciona bien para todos los casos. Con bien me refiero a sin errores... Por por ejemplo se me ocurre un escenario en el que no lo organiza bien del todo:
A = 5
B = 2
Haciendo para A:
redondeo(7.0 / 5.0) = redondeo(1.4) = 1
Metería los A en las cinco primeras posiciones... Pero se me ocurre que esto se puede solucionar ordenándolos de menor a mayor, es decir, haciendo primero B y luego A.

Y, en el caso anterior, primero A, luego B y por último C, a ver, haciéndolo de nuevo:
A = 2
B = 3
C = 5

aux[0] = 1
aux[1] = 2
aux[2] = 3
aux[3] = 4
aux[4] = 5
aux[5] = 6
aux[6] = 7
aux[7] = 8
aux[8] = 9
aux[9] = 10

Primero con A:
redondeo(10.0 / 2.0) = 5

Por lo que A va en las posiciones 0 y 5, correspondientes a las cajas 1 y 6, y el auxiliar quedaría:
aux[0] = 2
aux[1] = 3
aux[2] = 4
aux[3] = 5
aux[4] = 7
aux[5] = 8
aux[6] = 9
aux[7] = 10

Luego para B:
redondeo(8.0 / 3.0) = redondeo(2.6666) = 3

Por lo que B las metemos en las posiciones 0, 3, y 6 (correspondientes a las cajas 2, 5 y 9), quedando aux:
aux[0] = 3
aux[1] = 4
aux[2] = 7
aux[3] = 8
aux[4] = 10

Y C es trivial. Al final quedaría:
A-B-C-C-B-A-C-C-B-C

No sé, esto parece que funciona... En resumen es el mismo que te dije al principio, pero ordenando los grupos de menor tamaño a mayor tamaño.

Salu2.

EDIT:
De todas formas, esto tampoco es perfecto, imagínate el escenario:
A = 1
B = 6
El resultado final sería: A-B-B-B-B-B-B, y lo ideal hubiera sido algo así como: B-B-B-A-B-B-B... La verdad es que hacer bien este problema no es sencillo, quizá lo suyo es que busques por internet algoritmos ya estudiados, y acabarás antes xD. Quizá jugando con las medianas puedas llegar a una solución mejor, no sé, es tarde y no me da pa más la cabeza, suerte xD

1

elkaoD #6 Nov '11

Ehm, estáis sobrepensándolo creo. Yo lo haría tal que así:

A = 2
B = 3
C = 5

Pones primero el mayor:
CCCCC

Denoto los huecos con |:

C|C|C|C|C

Cada hueco entre las C (4 huecos) es un nuevo espacio. Rellenas desde el nodo más central con el siguiente por número (tienes que dar más peso a la izquierda o la derecha para los impares por cojones):

CBCBCBCC

Con huecos:

C|CB|CB|CB|C

Vuelves a hacer lo mismo, a la derecha del anterior

C|CBA|CBA|CB|C

No es perfecto pero es menos comedura de cabeza y da el pego, y si quieres que quede mejor, en las pasadas a partir de la 2 puedes hacer que la prioridad, despues del central, sea rellenar los huecos menos rellenos, para que quede mejor distribuído. Piénsalo como un árbol.

CA|CB|CBA|CB|C

n1x3r #7 Nov '11

Las respuestas que me dais ya las pensé antes e investigue como hacelo, aqui dejo algo de codigo residual de la idea principal:

$foto = 15;
$noticia = 10;
$video = 5;
$musica = 3;
$cine = 2;
//$longitud = 30;
$total = $foto + $noticia + $video + $musica + $cine;
echo $total;
//$tiempo = $total / $longitud;
/*
$video = round(($video / $longitud) * 100);
$musica = round(($musica / $longitud) * 100);
$foto = round(($foto / $longitud) * 100);
*/

$video = round($total / $video);
$musica = round($total / $musica);
$foto = round($total / $foto);
$noticia = round($total / $noticia);
$cine = round($total / $cine);

$video_t = $video;
$musica_t = $musica;
$cine_t = $cine;
$noticias_t = $noticias;
$foto_t = $foto;
$string = "";
$total = $total;
for($i=0; $i<=($total);){
/*
if($i >= $foto_t){$string .= "I"; $foto_t = $foto_t + $foto;}else{
if($i >= $noticia_t){$string .= "N"; $noticia_t = $noticia_t + $noticia;}else{
if($i >= $video_t){$string .= "V"; $video_t = $video_t + $video;}else{
if($i >= $musica_t){$string .= "M"; $musica_t = $musica_t + $musica;}else{
if($i >= $cine_t){$string .= "C"; $cine_t = $cine_t + $cine;}
}}}}*/
if($i >= $foto_t){$string .= "I"; $foto_t = $foto_t + $foto;}
if($i >= $noticia_t && (($noticia_t + $noticia) < $total)){$string .= "N"; $noticia_t = $noticia_t + $noticia;}
if($i >= $video_t && (($video_t + $video) < $total)){$string .= "V"; $video_t = $video_t + $video;}
if($i >= $musica_t  && (($musica_t + $musica) < $total)){$string .= "M"; $musica_t = $musica_t + $musica;}
if($i >= $cine_t  && (($cine_t + $cine) < $total)){$string .= "C"; $cine_t = $cine_t + $cine;}
$i++;
}
//echo $video;
echo $string;
echo strlen($string);
//echo "<br>" . $tiempo;
//echo "<br>" . $video;
//echo "<br>" . $musica;
//echo "<br>" . $foto;

Pero no conseguía hacerlo correctamente, me da algo como a vosotros, algo que da "el pego" pero busco algo mas homogéneo aun, busco la perfecion, pensad que estáis jugando con 10 cajas y tres elementos, cuando yo en realidad tengo que usar 720 cajas y cientos de elementos.
Seguro que tiene q existir alguna función ya preparada para estos casos pero no la encuentro por ningún lado, seguire buscando, cuando lo tenga lo pondre aqui.
Un saludo y gracias.

Thanat0s #8 Nov '11 Cofrade

No sé porqué me da pero tú buscas algo parecido al problema del cambio de programación dinámica, ¿no?

1

PiradoIV #9 Nov '11 Brongster

No me queda clara una cosa, por un lado pones que quieres:
C-B-C-A-C-B-C-A-C-B

Pero al principio pones:
foto, foto, video, foto, foto, video, musica, foto

Que sería:
C-C-B-C-C-B-A-C-C-B

Este código sería para el primero:


<?php
#
# La dispersión homogénea quedaría así: C-B-C-A-C-B-C-A-C-B
#

# Cuántos items quieres mostrar en total
$maximo = 100;

# Para manejar las iteraciones
$contador = 0;
$i = 0;
$separador = "-";

# La función que imprime el resultado
function mostrar($tipo) {
	global $contador, $maximo, $separador;
	
# Comprobaciones antes de hacer nada
$validos = array('foto', 'video', 'musica');
if(!in_array($tipo, $validos)) return FALSE;

# Aunque en medio del bucle principal
# pidamos mostrar un gritón de veces algo,
# no se mostrará si ya hemos llegado
# al límite
if($contador >= $maximo) return FALSE;

# Todo está correcto, mostramos el item
echo $tipo;

# Si el item que hemos mostrado no
# es el último, mostramos el separador
if(++$contador != $maximo) echo $separador;

}

# Bucle principal
while($contador < $maximo) {
	
# Siempre mostramos una foto
mostrar("foto");

# Después de cada foto, mostramos
# un video o una música
if($i++ % 2 == 0) {
	mostrar("video");
} else {
	mostrar("musica");
}

}

echo "\n";

1 respuesta

elkaoD #10 Nov '11

#9 hombre, eso es un poco chapu, sólo funciona si hay tantas fotos como la suma de vídeos y música, ¿no?

PiradoIV #11 Nov '11 Brongster

Sí, claro, se podría quedar pillado el bucle y además imprime el resultado directamente en pantalla... pero supongo que para la idea le va a valer, desde luego no se acerca a un código de producción definitivo.

Ulmo #12 Nov '11

Yo es q veo muchas formas de hacerlo, otra forma es trabajar con pilas o colas:

Cojes el elemento de mayor número C = 5 y lo apilas, por definicion, una pila de 5 elementos iguales es homogénea.
Cojes el siguiente elemento B = 3, para colocar 3 objetos tienes q partir el grupo q tienes de altura 5 en 4 partes iguales: 5/4 = 1,25. Y comienzas a desempilar:
1,25 = desempilas 1, colocas B y te guardas 0.25
1,25 + 0,25 = desempilas 1, colocas B y te guardas 0.5
1.25 + 0.5 = desempilas 1, colocas B y te guardas 0.70
1.25 +0.75 = desempilas 2.
Ahora lo mismo con A = 2 sobre una pila de 8 elementos. 8/3 = 2,6 y repites.

Como siempre partes un conjunto homogéneo en partes enteramente homogéneas ( nunca pueden ser 100% homogeneas si no puedes hacer decimales), el resultado siempre es un conjunto enteramente homogéneo.

¿no?

1 3 respuestas

BLZKZ #13 Nov '11

esto no es como el problema de la mochila? xD

2 respuestas

elkaoD #14 Nov '11

#12 me ha gustado tu solución.

#13 nope, el problema de la mochila no implica orden alguno.

n1x3r #15 Nov '11

#12 la solución parece bastante factible, pero explícame que haces cuando tienes dos conjuntos con el mismo valor digamos que A y C valen 5

1 respuesta

elkaoD #16 Nov '11

#15 se elige cualquiera de los dos como el inicial, da igual, y el algoritmo funciona de la misma forma.

Thanat0s #17 Dic '11 Cofrade

#13 Se parece más al problema del cambio xD

n1x3r #18 Dic '11

#12 me lo podrías desarrollar un poco, porque no logro entenderlo por completo, dices que en la tercera B desempilas 1 cuando tendrías que desempilar 2 al igual que en la segunda B no?

1 respuesta

Rivendel #19 Dic '11 Penitente

A mi se me ocurre que los pongas en orden, estilo A-A-A-B-B-C-C-C y apliques un algoritmo de sustitución con números aleatorios las pasadas que quieras hasta que quede algo potable.

n1x3r #20 Dic '11

y como sabe el programa que es algo potable? con el propio algoritmo que busco en si xd

Ulmo #21 Dic '11

#18 ¿Porque? La tercera B es 1.25 + 0.5 = 1.75, no llegas a llenar el entero para llegar a 2, por lo tanto desempilas uno y te guardas 0.75 para la siguiente q ya sí q serîa 1.25 + 0.75 = 2, y desempilas 2.

A veces parece q no queda visualmente homogéneo, pero si te lo miras bien, creo q siempre queda 100% homogéneo dentro de las posibilidades q ofrecen los números enteros, ya q siempre aplicas una misma lógica:

Si partes un conjunto homogéneo en partes iguales, te quedan iguales partes homogéneas.

n1x3r #22 Dic '11

He revisado e intentando montarlo en php pero existen algunos problemas por ejemplo, si tienes q repartir 2, y quieres ahcerlo de forma homogenea entre 9 por ejemplo, lo normal es que salga asi 123N456N789 con tu algoritmo se empezaria desde la mitad, por lo que los numeros pares su primera posicion se tiene que contar desde N/2 entonces eso ya me descuadra todo un poco, si todos los numero fuesen impares pues bien, perfecto, pero al no serlo me jode todo.

1 respuesta

Ulmo #23 Dic '11

#22 No lo entiendo, con 2 y 9 sigue saliendo perfecto:

Apilo 9 cosas, y tengo una cosa homogénea de 9 objetos.
Cojo 2 objetos, y como tengo q romper el conjunto en 3 partes para meter 2 objetos homogéneamente 9/3 = 3:
0+3 = 3 -> Desempilo 3 y coloco el primero.
0+3 = 3 -> Desempilo otros 3 y coloco otro.

Ya he acabado. Precisamente cuando tienes n-1 objetos múltiplos del tamaño de la pila, queda perfectamente homogéneo, el problema es cuando tienes q arrastras el residuo de hacer la división entera.

1

Se me presenta un reto y no se por donde cogerlo

Usuarios habituales

Tags