Algoritmo combinatoria string

[Swimpiii]

Buenas tardes mentes pensantes,

Les describo lo que deseo conseguir (tiene que ver con los cruzamientos prueba de Mendel, a alguno os sonará):

Tengo(después de un proceso anterior) un string de tamaño variable entre 2 y 20 caracteres. Necesito obtener todas las combinaciones posibles de dichos caracteres SIN alterar su posición (vienen ordenados) según si el carácter viene "repetido" o no (mayúscula y minúscula).

Como yo me explico malamente, que mejor que poner unos ejemplos:

EJEMPLO 1
------------------
cadena: 'AaBCcD'

Las combinaciones posibles serían: ABCD, ABcD, aBCD y aBcD.

EJEMPLO 2
------------------
cadena: 'ABcCdDEFf'

Las combinaciones posibles serían: ABCDEF, ABCDEf, ABCdEF, ABCdEf, ABcDEF, ABcDEf, ABcdEF y ABcdEf.


Dichas combinaciones me gustaría tenerlas guardadas en memoria ya que, además de mostrarlas por pantalla, también las necesitaría para posteriores cálculos. Por cierto, lo estoy haciendo en C.

Muchas gracias por su ayuda y su tiempo de antemano.

Un saludo

[engel lex]

si es un aporte, muestra el codigo, si es una duda, igual coloca lo que llevas de codigo (en etiquetas GeSHi) y explica tu duda o error

[Swimpiii]

Buenos días,

No tengo código realizado de eso que expongo. Es un algoritmo aparentemente sencillo que yo, como "nuevo" en esto de la programación, no acabo de ver la manera de hacerlo.

Por ello mi mensaje es captar ideas, formas de afrontarlo de alguien con más experiencia o conocimientos.

¿Alguien puede orientarme?

Un saludo y gracias de antemano

[avesudra]

Buenos días,

No tengo código realizado de eso que expongo. Es un algoritmo aparentemente sencillo que yo, como "nuevo" en esto de la programación, no acabo de ver la manera de hacerlo.

Por ello mi mensaje es captar ideas, formas de afrontarlo de alguien con más experiencia o conocimientos.

¿Alguien puede orientarme?

Un saludo y gracias de antemano

Sabes que las letras que cambian  (mayúscula y minúscula)  son n letras, entonces habrá 2ⁿ combinaciones posibles. Tengo el código que me ha costado un poco hacerlo, pero me ha salido tan feo que no sé si me he complicado la vida o qué. En esencia lo que he hecho ha sido mirar las letras que cambian, luego hago una plantilla de las letras que no cambian y las posiciones que van a sustituirse se indican por una coma.

Bueno voy a poner el código a ver si te ayuda porque es que no sé, creo que me he complicado la vida y que se puede hacer más sencillo. Bueh ahí va:

EI: Codigo reportado y borrado.

A los asesinos de código:

Si ustedes pretenden ser papá y mamá de cada usuario háganlo, no cae sobre mi responsabilidad la ética ni la moral de cada usuario, me sé perfectamente las normas del subforo, no venga a darme lecciones de lo que debo o no debo hacer.

Soy una persona muy comprensiva, pero ustedes se están cargando el subforo. Esto lo pongo en mayúsculas por si no les queda a ustedes claro:

SE PUEDE DISTINGUIR PERFECTAMENTE ENTRE UNA PERSONA QUE PIDE LAS TAREAS EXPLÍCITAMENTE Y OTRA QUE QUIERE APRENDER.

Si no entienden los mensajes, no entra bajo mi responsabilidad la capacidad de compresión lectora de cada Usuario/Moderador.

Este subforo se está convirtiendo en un estercolero de errores de sintaxis sin algo más novedoso, y eso lo estan provocando ustedes ¿porqué cuando algunos de ustedes ponen código no pasa absolutamente nada?

Han cabreado ya a muchos usuarios por el mismo tema, se están pasando ustedes de la raya, se está yendo mucha gente que podría ser de provecho en el foro.

Me niego a seguir respondiendo dudas de sintaxis sencilla, que lo hagan Eternal Idol y demás.

Así que por lo demás, teneis otro forero más que va al cubo de la basura en este subforo.

[Eternal Idol]

De lo anterior se desprende que sabiendo las reglas algunos INCONTINENTES del codigo deciden romperlas y cuando se les aplican las mismas deciden irse del subforo. Muy bien, personalmente les digo que no se los extraña en lo mas minimo sino que muy por el contrario se les agradece su deferencia al ahorrarme trabajo innecesario.

avesudra le deseo mucha suerte respondiendo dudas complejas y novedosas a donde quiera que se vaya, usted si que sabe.

[avesudra]

De lo anterior se desprende que sabiendo las reglas algunos INCONTINENTES del codigo deciden romperlas y cuando se les aplican las mismas deciden irse del subforo. Muy bien, personalmente les digo que no se los extraña en lo mas minimo sino que muy por el contrario se les agradece su deferencia al ahorrarme trabajo innecesario.

avesudra le deseo mucha suerte respondiendo dudas complejas y novedosas a donde quiera que se vaya, usted si que sabe.

El problema no es la sintaxis sencilla, yo aprendí preguntando en este magnífico foro y sigo aprendiendo, y me encanta ayudar a la gente, me parece raro que nunca te haya leído en algún tema relativamente sencillo, quizás es que como no es de tu nivel no debes responderlo, claro como eres moderador, que a eso se dediquen otros. Lo que he dicho de la sintaxis es en lo que te fijas para defenderte y atacar una prepotencia que no existe, ni que yo fuese aquí Dennis Ritchie. El problema es que cuando sale algún problema más complejo que un punto y coma o algo de eso, si se pone código se borra y si se debate, se cierra el tema.

Yo no sé nada, es más, por día me doy cuenta de que sé menos.

Haz lo que quieras, es curioso que tengas tiempo de estar borrando códigos en lugar de estar ayudando por ejemplo en este hilo, además es algo irónico que en un Subforo de Programación en C, no se aporten códigos, entonces exijo que se cree un subforo de algoritmia porque es lo que se está pidiendo. Es decir a ver si me explico, si yo hubiese puesto un recetario de pasos no me borrais nada ¿verdad?

Y efectivamente, tu trabajo borrando códigos es totalmente innecesario si no se pide la tarea explícitamente (de forma directa poniendo el enunciado).

Porque repito que se ve claramente quien viene con intenciones de aprender y quien no, si no ves eso estás ciego.

Muchos foreros tienen el mismo problema y siempre los que pensamos diferente pasamos a ser ignorados sin proponer ninguna solución respecto al tema bajo tu estricta inflexibilidad respecto de alguna puntualización sobre las normas.

avesudra le deseo mucha suerte respondiendo dudas complejas y novedosas a donde quiera que se vaya, usted si que sabe.

No trates de ponerme de listo porque no lo soy.

[Eternal Idol]

Antes se negaba, ahora exige y habla de una prepotencia que no existe, en fin ... le aclaro que cuando realmente quiero responder a lo que alguien dice lo hago detalladamente, punto por punto y citando al usuario en cuestion, no es el caso ya que no le doy entidad. Ademas este tema ya esta saldado, la discusion fue dada en repetidas ocasiones, asi que simplemente me limite a hacer un comentario sarcastico.

PD. No desvie mas el hilo si todavia no se desahogo lo suficiente lo invito a enviarme un mensaje privado (aunque no prometo leerlo y mucho menos responderlo).

[Swimpiii]

Buenas tardes...

Veo que ha habido algún problema con mi algoritmo...

Muchas gracias Avesudra por tu intento de aclararme el tema, pero tristemente ayer no entré en el foro y no pude ver el código que expusiste...

No me importa si es complejo o no, quiero ver alguna forma de afrontarlo. Por tanto, si parece ser que en estos foros no se puede escribir código fuente por política de los mismos, ruego que por favor me envíes ese código por privado.

En el caso de que eso también sea "ilegal" o no lo tengas ya, si puedes comentarme con palabras lo que realizaste me harías un gran favor...

Muchas gracias de antemano, un saludo

[engel lex]

yo lo haría de la siguiente manera... recorres la cadena ingresada, buscando los fijos y los intercambiables, para meterlos en 2 arrays

seria algo como

Código [Seleccionar] Expandir

si cadena[a] == cadena[a+1]+32
32 es la diferencia de posiciones ascii entre mayusculas y minusculas

cadena: 'ABcCdDEFf'
fijos: 'AB**E*'
intercambios: 'CDF' no importa las minusculas, porque se saben que son de ellos...

donde n es la cantidad de intercambios haces 2 ciclos anidados

Código [Seleccionar] Expandir

x desde 0 hasta < 2^n

Código [Seleccionar] Expandir

y desde 0 hasta < n

con eso puedes hacer un juego en binario para escoger las letras correctas, aquí un ejemplo

Código (cpp) [Seleccionar] Expandir

int main() {
   char intercambios[] = "ABC";
   int x,y,a;
   char buff[3];
   for(x=0;x<8;x++){
    for(y=0;y<3;y++){
    a = 32*((x>>y)&1);
    buff[y] = intercambios[y]+a;
    }
    //imprimir aqui buff para ver el resultado
   }
}

la operacion ((x>>y)&1) lo que hace es lo siguiente, desplaza "x", "y" bits a la derecha, luego hace un "and" 1 para que el resultado sea 1 o 0... esta es la forma más simple de hacer combinatorias de 2 opciones ya que en binario se hacen por naturaleza

de resto, solo te falta sustituir asteriscos por el contenido de buff y estás resuelto