Combinatoria C#

glolg #1 Feb '13

Buenas,
estoy haciendo una pequeña aplicación como reto que me han propuesto sobre hacer una aplicación, al principio con un array con el abecedario en minúsculas y números, indicar la longitud del string y generar todas las posibles combinaciones con el array.

Hasta aquí bien, con una función recursiva lo he conseguido, el problema viene cuando pones más de 3 caracteres de longitud, donde se tira la vida para mostrar los resultados. Mi intención es que vayan saliendo en pantalla conforme se generan. Lo que no doy con el método.
Os muestro el código

Como variables globales tengo la longitud del carácter y el array.

        int longi;
        string[] posibles = new string[] {"0","1","2","3","4","5","6","7","8","9", 
                    "a","b","c","d","e","f","g","h","i","j", 
                    "k","l","m","n","o","p","q","r","s","t", 
                    "u","v","w","x","y","z"};

Al tener el objeto listbox, he creado una función que no devuelve nada (void) y va añadiendo a la lista mediante un item add los resultados.

        private void combinacion(string cadena, int longitud) {
            string caracter;
            string aux;

        if (longitud == 0){
            listBox1.Items.Add(cadena);
        }else{
            for (int i = 0; i < posibles.Length; i++)
            {
                caracter = posibles[i];
                aux = cadena + caracter;
                if(aux.Length == longi) listBox1.Items.Add(aux);
                combinacion(aux, longitud - 1);
            }
        }
        
    }

Y aquí el botón de acción por donde le paso los parámetros a la función

        private void button1_Click(object sender, EventArgs e){
            combinacion("", int.Parse(textBox1.Text));
            longi = int.Parse(textBox1.Text);
            MessageBox.Show("Ya ha terminado, hay "+listBox1.Items.Count+" combinaciones");
        }

El problema como he dicho, es que no va escribiendo mediante va calculando, sino que se espera al final.
Se me ha ocurrido meterle un progressbar para que vaya indicando el progreso, pero la aplicación se queda parada mientras calcula. Eso no gusta!

Si alguien sabe como arreglarlo me daría una gran alegría
Saludoss.

APOCa #2 Feb '13

No me acuerdo ya de c#, lo vi hace años pero diría que eso lo tienes que hacer con un background worker

1 respuesta

Meleagant #3 Feb '13 :psyduck:

el problema viene cuando pones más de 3 caracteres de longitud, donde se tira la vida para mostrar los resultados

Normal, porque estás usando una función recursiva, que es de todo menos óptimo.

Conviértela a iterativa y verás la diferencia.

1 respuesta

Soltrac #4 Feb '13 MV Wizard

#3 ???

No es por eso, una función iterativa y la misma recursiva tienen el mismo orden. No vas a notar diferencias (obviamente las hay, pero se consideran despreciables al calcular la bondad del algormitmo).

Respecto al tema de #1, puedes hacerlo, a la forma bonita o a la forma mal y fácil.

Te paso la forma MAL pero sin embargo fácil de hacerlo: Cada vez que quieras que se refresque lo q hay en pantalla añade un "Application.DoEvents()".

2 respuestas

glolg #5 Feb '13

#4 genial logro el efecto que buscaba. Igualmente me miraré lo que dice #2 y haré una prueba estática con el método recursivo e iterativo cronometrando haber si existe mucha diferencia. También estoy buscando una librería que me permita trabajar con GPU para acelerar el proceso.

1 respuesta

LOc0 #6 Feb '13

Offtopic de #4 Si es tail-recursion, sí, iterativo ~ recursivo.

spoiler

#include <stdio.h>

int main()
{
	printf("5! = %d\n", factorial_rec_normal(5));

printf("5! = %d\n", factorial_rec_tail(5, 1));

return 0;
}


int factorial_rec_normal(int n)
{
	if(n == 0)
		return 1;
	else
		return n*factorial_rec_normal(n-1);
}


int factorial_rec_tail(int n, int acumulador)
{
	if(n == 0)
		return acumulador;
	else
		return factorial_rec_tail(n-1, acumulador*n);
}

Salu2

1

Soltrac #7 Feb '13 MV Wizard

#5 Para controlar tiempos, usa TimeSpan

DateTime start = DateTime.Now();
// Super algoritmo
DateTime end = DateTime.Now();
TimeSpan ts = end - start;
MessageBox.Show(ts.TotalMiliSeconds.ToString());

Combinatoria C#

Usuarios habituales

Tags