combinatorias

[webpedaler]

si tenemos un conjunto A={a,b,c,d}, ¿cuántos subconjuntos de 2 elementos cada uno se pueden obtener?

Haciéndolos se obtienen: {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}. Son seis los subconjuntos

bueno para saber las combinaciones 4! / 2!(4-2)! = 6
dado por n! / r! (n-r)!

ahora mi problema es como dibujo los subconjuntos que se prodrian dar aplicando n! / r! (n-r)!

[Cluster]

Viva las matemáticas XDD

Mi fuerte no son las matemáticas .. pero no sé donde tienes el problema si sabes aplicar tu ecuación .. Es decir .. tus elementos los puedes almacenar en un array para estas operaciones .. dispones de bucles foreach() para recorrer ese array y un buen montón de funciones para operaciones con arrays que tal vez combinandolas te puedan ayudar ...

www.php.net/array

Un saludo,

[josemi]

Hola,

Bueno, para 2 es relativamente sencillo. Solo tienes que coger los elementos de 1 a n-1, y emparejarlo con los elemento de i+1 a n, siendo n el numero total de elementos, e i el elemento en curso.

Como estamos en PHP, aqui va el codigo en dicho lenguaje:

Código PHP:

  $a=array('a','b','c','d');
$n=count($a);
for($i=0;$i<($n-1);$i++) {
  for($j=($i+1);$j<$n;$j++) {
    echo $a[$i].' - '.$a[$j].'<br>';
  }
} 
   

si no tengo oxidado el cerebro.

Para 3 supongo que sera añadir un nivel mas de anidamiento.

Por supuesto, ya habra un algoritmo generico para r elementos. Intenta buscar 'algoritmo combinatoria' o 'metodos numericos combinatoria' en google.

Saludos.

PD: Si no lo querias en PHP, lo dices y muevo el mensaje al foro de programacion.

[webpedaler]

Mensaje Original por josemi
Hola,

Bueno, para 2 es relativamente sencillo. Solo tienes que coger los elementos de 1 a n-1, y emparejarlo con los elemento de i+1 a n, siendo n el numero total de elementos, e i el elemento en curso.

Como estamos en PHP, aqui va el codigo en dicho lenguaje:

Código PHP:

  $a=array('a','b','c','d');
$n=count($a);
for($i=0;$i<($n-1);$i++) {
  for($j=($i+1);$j<$n;$j++) {
    echo $a[$i].' - '.$a[$j].'<br>';
  }
} 
   

si no tengo oxidado el cerebro.

Para 3 supongo que sera añadir un nivel mas de anidamiento.

Por supuesto, ya habra un algoritmo generico para r elementos. Intenta buscar 'algoritmo combinatoria' o 'metodos numericos combinatoria' en google.

Saludos.

PD: Si no lo querias en PHP, lo dices y muevo el mensaje al foro de programacion.

mmmm es justo lo que busco , un algoritmo que me sirva para N Y R, en tu ejemplo N estaria siendo los elementos del array y r seria el problema ,debido a los anidamientos , por ahi va la cosa si pillo algo lo posteo.
lo màs chistoso es que despues de pintar esas combinaciones , debo de hacer grupos de a 4 sin que se repitan los elementos de esos conjuntos.

osea tomando el jemplo anterior donde n=4 y r= 2

{a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}.

debo de hacer esto :
{a,d}, {b,c}

{a,c}, {b,d}

{a,b}, {c,d}

en este caso solo se pueden formar grupos de a 2 sin que se repitan los elementos .

muajaja me quiero morir jajaja
quien dijo que las matematicas no servian?

[tomerqueves]

No sé que problema hay en revivir temas pero espero que no sea una falta grave cuando meinteresa el tema.
resulta que estoy haciendo una ouija electronica y he pensado que la combinatoria es una forma muy buena para salvar la incertidumbre.
Si alguien me dice como se anidaría para 3 elementos supongo que para cuatro ya me apañaría solo.
Gracias.

[HackmanC]

Hola,

Iniciado por tomerqueves

... Si alguien me dice como se anidaría para 3 elementos supongo que para cuatro ya me apañaría solo. ...

El tema normalmente es mas complejo de lo que parece, principalmente porque los términos son bastantes confusos, combinatiorias, permutaciones, etc., y entre estas se dividen o se conjugan con diferentes factores como por ejemplo, con repetición y sin repetición, etc.

Ya tienes un ejemplo de combinaciones (coeficiente binomial, según la fórmula que se mostró anteriormente), si con ese ejemplo de 2 no sacaste el de 3, ¿que te hace pensar que con 3 sacas el de 4? Aunque posiblemente te sea de alguna ayuda:

http://www.forosdelweb.com/f18/desaf...3/#post4433005

El algoritmo solo funciona para N cantidad, dependiendo del nivel de anidación del ciclo, por lo que no es muy versátil aunque es simple de implementar.

Adicionalmente que su funcionamiento es exponencial, es decir, para un nivel de anidación de 8 o mas se va a tomar un buen tiempo. Normalmente es preferible optar por una solución diferente en la mayoría de los casos, a menos que tu objetivo esté claramente definido por la necesidad de hacer combinaciones, permutaciones o variaciones.

Por ejemplo, permutaciones en lenguaje C optimizado:
http://www.forosdelweb.com/f96/petan...ml#post4660490
En mi solución de permutaciones tomaría 30 o mas minutos la solución, mientras que si lees las propuestas de los demás y los resultados no pasa de 2 minutos, el problema es que normalmente los algoritmos de combinaciones son muy lentos por los cálculos intermedios que hay que realizar (aunque se optimizara más el código, creo no bajaría de 5 minutos).

Saludos,

ps:

Lo que solicitaba webpedaler originalmente hace como 10 años era una algoritmo que funcionara para cualquier variable para N y R (y creo que una mezcla extraña para mostrar los resultados); y esa es otra historia levemente mas compleja.

[tomerqueves]

Tendré que usar google y ver si mi idea sse adapta a cualquiera de tus tres opciones mejor que a la combinatoria pura.
De todos modos te agradezco en sobremanera tu pronta respuesta y me has ayudado mucho.

Solo que pienso que el anidamiento de bucles for se podría también solucionar con recursividad y así me daría un numero de N letras a combinar dinámicos.

si no recuerdo mal la recursividad se llamaba dentro de simisma en la funcion y ademas hacía otra cosita más ... supongo que una funcion recursiva que se llame a si misma y haga la formula de la recursividad será lo que necesito pero no se interpretar los sumatorios y es el un problema.


Lo que quiero para que se vea mi idea es que el sistema arroje unas posibles soluciones a qué puede estar haciendo la OUIJA y sea el usuario quien pedio de check´s vaya definiendo lo que es la palabra o palabras que la ouija va diciendo.

funcion recoje (array)
{
combina (recoje)
{
definición de combinatoria + recoje (array);
}
}

Eso sería la pseudo idea.
Tengo que probar si funciona pero por el momento ya tengo más para trabajar de lo que soy capaz de dijerir. De modo que muchas gracias.

[HackmanC]

Hola,

Iniciado por tomerqueves

Tendré que usar google y ver si mi idea sse adapta a cualquiera de tus tres opciones mejor que a la combinatoria pura. ...

A eso me refería, puede ser que necesites algo diferente que no sea combinatoria, o puede que si, dependerá de lo que quieres hacer. Aunque los conceptos estadísticos son bastante simples, lo difícil a veces es crear los algoritmos que generen la secuencia de combinaciones o lo que sea que necesites.

Iniciado por tomerqueves

... Solo que pienso que el anidamiento de bucles for se podría también solucionar con recursividad y así me daría un numero de N letras a combinar dinámicos. ...

Es cierto, con recursividad se resuelve parte del problema, dependiendo de las características del problema. Puede ser que en tu caso se pueda resolver fácilmente o puede que no. El principal problema que vas a encontrar, creo, es la forma de mostrar el resultado, si observas detenidamente se hace uso de los 3 indices al mismo tiempo, eso es algo que no se puede obtener recursivamente, sin pasar la misma cantidad de parámetros a la función recursiva que la cantidad de anidación del ciclo for.

Iniciado por tomerqueves

... Lo que quiero para que se vea mi idea es que el sistema arroje unas posibles soluciones a qué puede estar haciendo la OUIJA y sea el usuario quien pedio de check´s vaya definiendo lo que es la palabra o palabras que la ouija va diciendo. ...

En ese caso posiblemente son permutaciones, por ejemplo con E, P y Z. Podrías obtener EPZ pero también PEZ, cosa que no sucede con las combinaciones o por lo menos con el algoritmo anteriormente descrito. Aunque no estoy seguro como funciona eso de las palabras, si importa el orden o no.

Iniciado por tomerqueves

...
funcion recoje (array)
{
combina (recoje)
{
definición de combinatoria + recoje (array);
}
}

Eso sería la pseudo idea. ...

El problema que observo, a simple vista, con ese algoritmo es que en la línea donde tendrías que imprimir el resultado no tienes acceso a los indices anteriores; es decir, si le pasas i, j, k, para imprimir array[i] + array[j] + array[k]; tendrías el mismo problema que los 3 bucles anidados, pero en este caso necesitas 3 parámetros.

No digo que no se pueda resolver, simplemente que es un poco mas complejo, y normalmente es bastante lento, las permutaciones de 8 letras son 8! = 40,320. Lo único que tendrías que hacer es definir bien el concepto de lo que quieres hacer y ver si estos métodos son factibles.

Saludos,

ps:

Pero como mencioné depende de lo que quieras lograr, por ejemplo:
http://www.forosdelweb.com/f13/como-...2/#post4648371
En ese ejemplo puedes ver como obtener una forma de combinación recursiva (usando Javascript, para un problema específico), la parte que no me termina de convencer en ese caso es que hay que ir guardando los resultados temporalmente en un array adicional.

[Diang]

Hola yo tengo un problema parecido, dado un conjunto de "m" caracteres mostrar todos los subconjuntos de "n" elementos que se pueden crear a partir de los caracteres del primero, por ejemplo:
Teniendo A={a,b,c,d}
entonces m=4 y si n=2 la solución seria: {a,b}{a,c}{a,d}{b,c}{b,d}{c,d}
Tengo que mostrar eso en pantalla y ya.
La verdad es que iterativamente ya se me ha ocurrido usando 3 ciclos y todo, el problema es que me lo exigen que lo resuelva con recursividad, y ya se que cualquier método iterativo se puede hacer recursivo, pero en serio que esto de la recursividad aun me confunde bastante.
No se si a alguien de ustedes se le ocurre algo o me pueden dar un empujón porque estoy bien atorado :(
Y se que esta sección es de PHP pero yo programo en C# y si me pudieran ayudar en ese lenguaje o en Java se los agradecería muchísimo.
Gracias de ante mano.

[dashtrash]

Se *tiene* que hacer con recursividad.Las soluciones anteriores que usan ciclos...
A ver, sea como sea que quieras hacerlo, con importancia del orden, sin importancia del orden, con repeticion, sin repetición, todo se reduce a:
1) Tienes ya una parte de la solución : (inicialmente, está vacía)
2) Tienes una serie de elementos que puedes añadir a la solución actual (dependiendo del orden/repeticion,etc) : inicialmente, todos los elementos.

La función recursiva es:
1) Si la solución actual tiene la longitud deseada, devolverla.
2) Por cada uno de los elementos que podemos usar para generar nuevas soluciones:
-2.1 crear una nueva solución como la actual + elemento.
-2.2 determinar cuales, de la lista de elementos, son válidos para añadir a nuevas soluciones.
-2.3 llamar recursivamente, con la solucion de 2.1, y la lista de 2.2

Código PHP:

Secuencia para [a,b,c,d] :
LLamada inicial: [],[a,b,c,d]
(Bucle)
     2.1 : [a]
     2.2   [b,c,d]
     2.3  LLamada recursiva [a],[b,c,d]
             2.1 [a,b]
             2.2 [c,d]
             2.3 LLamada recursiva [a,b],[c,d]
                   <retorno: longitud=2>
             2.1 [a,c]
             2.2 [d]
             2.3 LLamada recursiva [a,c],[d]
                   <retorno: longitud = 2 >
             2.1 [a,d]
             2.2 []....
     2.1 [b]
     2.2 [c,d]
     2.3 LLamada recursiva [b],[c,d]
           .....
      2.1 [c]
      2.2 [d]
      2.3 LLamada recursiva [c],[d]
     ....
 

Obviamente, la comprobación de la longitud de la solución se puede hacer antes de llamar a la función recursiva, pero es menos "purista"