Foro de elhacker.net

Hola, este es mi primer mensajito jeje, me he visto obligado a pedir ayuda, al principio me veía capaz, pero después de probar mil códigos diferentes y ver que siempre todos fallan en algún punto acudo para pedir que me echéis una mano, plissss.

El caso, tengo un array (correctamente inicalizado y comprobado que contiene bien los caracteres y todo ok), así, suponiendo que contiene los caracteres; a b c d, el programa debe hacer las siguientes combinaciones:

ab
ac
ad
bc
bd
cd
abc
abd
bcd
abcd

Nota: si se conoce el número de caracteres es relativamente sencillo, pero se trata de hacer combinaciones del modo que explico sin saber el número de caracteres, es decir, el usuario introduce por teclado el número, y a continuación los caracteres, pero el código del programa debe estar preparado para funcionar sea cual sea el número, si no me explico me lo decís jeje.

No importa el orden, únicamente importa que estén todas las combinaciones. Me extraña que no haya ningún algoritmo ya desarrollado que haga esto, ¿no tiene ningún nombre realizar combinaciones de esta manera?, pregunto par poder googlear jeje.
Bueno, si a alguien se le ocurre cómo hacerlo, aunque sea la idea, no es necesario que me de el código, se lo agradezco mucho. El programa es en C, aunque si alguno sabe hacerlo en otro lenguaje que lo haga en ese y ya lo "traduciremos" jeje.

Muchísimas gracias. Saludos.

Si quieres que haga todas las combinaciones de unos caracteres puede buscar por fuerza bruta.
Lo del numero a que te refieres?

Yo ya lo tengo hecho y realizado:

Recursivo:

const char Diccionario[]= {'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','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','0','1','2','3',
'4','5','6','7','8','9','\0'};
 
const int Tamanyo_Diccionario;
 
//...
 
Tamanyo_Diccionario = strlen(Diccionario);
 
// Llamamos a la funcion
 
while(!explora(intento,password,0,hasta)) { hasta++;
    intento[hasta] = '\0';}
 
printf("La contrasenaya es: %s",intento);
 
//...
 
char explora (char* Password,const char* Correcta, int desde, int hasta){
  if (desde==hasta){
    return !strcmp(Password,Correcta);
  }else{
    int i = 0;
    for (i=0; i< TamanyoDiccionario; i++){
      Password [desde] = Diccionario[i];
       if (explora (Password, Correcta, desde+1, hasta))
        return 1;
    }
  }
  return 0;
}

Otra modalidad iterativa (lo usé para resolver sudokus y está en C++, tendrás que adaptarlo):

bool Resolver(short Tablero[MAX][MAX])
{
    vector<pair<int,int> > Casillas;
    for (short j = 0; j < MAX;j++)
        for (short i = 0; i < MAX;i++)
            if (Tablero[i][j] == 0)
                Casillas.push_back(make_pair(i,j));
 
    register short Inicio = Casillas.size()-1;
 
    short Actual;
    short i;
 
    for (i = 0; i < Casillas.size();i++)
    {
            Tablero[Casillas[i].first][Casillas[i].second] = i%(MAX)+1;
    }
 
   // Ultimo_Movimiento = 1;
 
    while(true)
    {
        for (i = 1; i < MAX;i++)
        {
 
            Tablero[Casillas[Inicio].first][Casillas[Inicio].second] = i;
 
            if (Resuelto(Tablero))
                return true;
        }
 
        Tablero[Casillas[Inicio].first][Casillas[Inicio].second] = 1;
 
        if (Inicio == 0)
                Inicio++;
        else
        {
            Actual = Inicio-1;
 
            Tablero[Casillas[Actual].first][Casillas[Actual].second] ++;
 
            while (Tablero[Casillas[Actual].first][Casillas[Actual].second] > (MAX))
            {
               Tablero[Casillas[Actual].first][Casillas[Actual].second] = 1;
 
                Actual--;
 
                if (Actual == -1)
                {
                    return false;
                }
                Tablero[Casillas[Actual].first][Casillas[Actual].second]++;
 
            }
 
        }
 
    }
 
}

Gracias a los dos, muchas gracias. Amchacon, te he enviado un mensaje con unos problemillas que tengo con tu programa, si no te importa, cuando tengas tiempo échale un vistacillo que estoy muy perdido jejeje.

Stakewinner00 lo que estoy tratando de hacer es un generador de fuerza bruta, lo que sucede es que ya tengo todas las partes principales del programa funcionando, solamente me falta ésta que os comento, lo cual no es fuerza bruta, pues son solamente algunas combinaciones de todas las posibles con esos caracteres. Aunque si alguno sabe de alguna manera (directamente, sin varias partes de código) de hacer todas las combinaciones posibles (fuerza bruta) de otra manera que lo diga porfa jejeje, que me adapto.

Con lo del número me refiero a que pueden ser 3 caracteres o 15, es decir, lo único en común es la manera de hacer las combinaciones, que es como explico en el ejemplo.

Saludos y gracias. :rolleyes:

Amchacon, he estado mirando tu programa, el que está en C, no el de C++, y me da errores de compilación, ¿qué compilador usas?

Además agradecería que alguien me explicara un poco el código, porque no entiendo bien el funcionamiento ni cómo está estructurado.

Saludos, gracias.

El código falta aplicarlo. Tienes que poner los includes necesarios, el main, etc.

Ya hombre, eso ya está hecho, además me lo mandó amchacon completo, pero ni con esas compila...

Postea aquí el código entero y te intentamos ayudar

#include <stdio.h>
#include <string.h>

const char Diccionario_Default[]= {'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','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','0','1','2','3',
'4','5','6','7','8','9','\0'};

const char Diccionario_Mayusculasoff[] = {'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','0','1','2','3','4','5','6','7','8','9','\0'};

const char Diccionario_Minusculasoff[] = {'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','0','1','2','3',
'4','5','6','7','8','9','\0'};

const char Diccionaro_Numerosoff[] = {'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','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','\0'};

const char Diccionario_MayusculasNumerosoff[]= {'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','\0'};

const char Diccionario_MinusculasNumerosoff[]= {'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','\0'};

const char Diccionario_MayusculasMinusculasoff[]= {'0','1','2','3','4','5','6','7','8','9','\0'};

char* Diccionario = Diccionario_Default;
int TamanyoDiccionario = 0;
char explora (char* Password,const char* Correcta, int desde, int hasta);

int main()
{
    char LongitudMin;
    char Opcion;
    char password[256];
    char intento[256] = "as";
    //char* valor = fgets(password,255,stdin);

    TamanyoDiccionario = strlen(Diccionario);
    puts("Introduce tu contrasenya: ");

    scanf("%s",password);

    puts("Quieres proporcionar opciones adicionales? (s/n): ");
    scanf(" %c",&Opcion);

    if (Opcion == 's' || Opcion == 'S')
    {
         char Mayuscula;
        char Minuscula;
        char Numeros;
        puts("Que longitud tiene al menos contrasenya? ");
        scanf("%d",&LongitudMin);

        if (LongitudMin < 0)
            LongitudMin = 0;

        puts("Tiene letras mayusculas? (S/N) ");
        scanf(" %c",&Mayuscula);

        puts("Tiene letras minusculas? (S/N)");
        scanf(" %c",&Minuscula);

        puts("Tiene numeros? (S/N)");
        scanf(" %c",&Numeros);

        #define Afr(tipo) (tipo == 's' || tipo == 'S')

        if (!Afr(Mayuscula) && !Afr(Minuscula) && Afr(Numeros)) // 001
            Diccionario = Diccionario_MayusculasMinusculasoff;

        if (!Afr(Mayuscula) && Afr(Minuscula) && !Afr(Numeros)) // 010
            Diccionario = Diccionario_MayusculasNumerosoff;

        if (!Afr(Mayuscula) && Afr(Minuscula) && Afr(Numeros)) // 011
            Diccionario = Diccionario_Mayusculasoff;

        if (Afr(Mayuscula) && !Afr(Minuscula) && !Afr(Numeros)) // 100
            Diccionario = Diccionario_MinusculasNumerosoff;

        if (Afr(Mayuscula) && !Afr(Minuscula) && Afr(Numeros)) // 101
            Diccionario = Diccionario_Minusculasoff;

        if (Afr(Mayuscula) && Afr(Minuscula) && !Afr(Numeros)) // 110
            Diccionario = Diccionaro_Numerosoff;

        if (Afr(Mayuscula) && Afr(Minuscula) && Afr(Numeros)) // 111
            Diccionario = Diccionario_Default;

        TamanyoDiccionario = strlen(Diccionario);// Generar Diccionario

    }
    else
        {
            LongitudMin = 0;
        }

    int hasta = LongitudMin;

    while(!explora(intento,password,0,hasta)) { hasta++;
    intento[hasta] = '\0';}

    printf("La contrasena es %s",intento);

    return 0;
}

char explora (char* Password,const char* Correcta, int desde, int hasta){
  if (desde==hasta){
    return !strcmp(Password,Correcta);
  }else{
    int i = 0;
    for (i=0; i< TamanyoDiccionario; i++){
      Password [desde] = Diccionario[i];
       if (explora (Password, Correcta, desde+1, hasta))
        return 1;
    }
  }
  return 0;
}

Pues ami si que me compila todo y que me da alertas podrías poner lo que te pone ati?
Ahora miro por que se trata, ya editare si eso.

EDITO: El error ocurre por que lo declaras como const

No estaría mejor declarar un array con todas las posibilidades y luego estableces las que el usuario elija?

error C2143: error de sintaxis : falta ';' delante de 'tipo'

error C2065: 'hasta' : identificador no declarado

error C2065: 'hasta' : identificador no declarado

error C2065: 'hasta' : identificador no declarado

EDITO: he quitado el const, pero da exactamente los mismos errores.

EDITO 2: amchacon, muy chula tu foto, es lo menos que podemos hacer por recordar a un genio al que nunca se le ha reconocido lo suficiente su trabajo y a quien no conoce esta sociedad en que vivimos, pero sí conoce a Steve Jobs, por ejemplo.

¿Has probado el código literalmente o has hecho algun cambio?

;)

¡Buenas!

Aquí te dejo otro código. Trabaja las combinaciones sobre un vector de enteros, ya que es lo único que te hace falta. Hacer combinaciones sobre un vector de cualquier cosa es hacer combinaciones sobre los indices del vector...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct t_combinatoria
{
    unsigned long **lista;
    unsigned long n_elementos;
    unsigned long longitud_elemento;
};
typedef struct t_combinatoria t_combinatoria;
 
void inicializar_combinatoria(t_combinatoria *c)
{
    c->lista = NULL;
    c->n_elementos = 0;
    c->longitud_elemento = 0;
}
 
void finalizar_combinatoria(t_combinatoria *c)
{
    unsigned long i;
 
    for(i = 0 ; i < c->n_elementos ; i++)
        free(c->lista[i]);
 
    free(c->lista);
 
    c->lista = NULL;
    c->n_elementos = 0;
    c->longitud_elemento = 0;
}
 
unsigned long factorial(unsigned long n)
{
    unsigned long ret = 1;
 
    while(n)
        ret *= (n--);
 
    return ret;
}
 
unsigned long n_sobre_k(unsigned long n, unsigned long k)
{
    return (factorial(n) / factorial(k)) / factorial(n - k);
}
 
int combinaciones(t_combinatoria *datos,unsigned long elementos_conjunto, unsigned long elementos_combinacion)
{
    static unsigned long indice = 0;
    static unsigned long elementos_fijados = 0;
    static unsigned long *aux = NULL;
    unsigned long i;
 
    if(!elementos_combinacion)
        return 0;
 
    if(indice == elementos_combinacion)
    {
        memcpy(*(datos->lista + elementos_fijados), aux, elementos_combinacion * sizeof(unsigned long));
 
        elementos_fijados++;
 
        return 1;
    }
 
    /* si es la primera vez que llamamos a la funcion, reservamos memoria para la tabla de combinaciones */
    if(!indice)
    {
        if(!(aux = (unsigned long *) malloc(elementos_combinacion * sizeof(unsigned long))))
            return 0;
 
        datos->n_elementos = n_sobre_k(elementos_conjunto,elementos_combinacion);
        datos->longitud_elemento = elementos_combinacion;
 
        if(!(datos->lista = (unsigned long **) malloc(datos->n_elementos * sizeof(unsigned long *))))
        {
            datos->n_elementos = 0;
            datos->longitud_elemento = 0;
 
            return 0;
        }
 
        for(i = 0 ; i < datos->n_elementos ; i++)
        {
            if(!(datos->lista[i] = (unsigned long *) malloc(datos->longitud_elemento * sizeof(unsigned long))))
            {
                int j;
 
                for(j = 0 ; j < i ; j++)
                    free(datos->lista[i]);
 
                free(datos->lista);
                datos->lista = NULL;
 
                datos->n_elementos = 0;
                datos->longitud_elemento = 0;
 
                return 0;
            }
        }
 
        for(i = 0 ; i < elementos_conjunto - elementos_combinacion + indice + 1; i++)
        {
            aux[indice] = i;
 
            indice++;
 
            combinaciones(datos, elementos_conjunto, elementos_combinacion);
 
            indice--;
        }
 
        free(aux);
        aux = NULL;
        elementos_fijados = 0;
        indice = 0;
    }
    else
    {
        for(i = aux[indice - 1] + 1 ; i < elementos_conjunto - elementos_combinacion + indice + 1; i++)
        {
            aux[indice] = i;
 
            indice++;
 
            combinaciones(datos, elementos_conjunto, elementos_combinacion);
 
            indice--;
        }
    }
 
    return 1;
}
 
int main(int argc, char *argv[])
{
    unsigned long i,j,k;
    t_combinatoria comb;
    char *vocales = "aeiou";
 
    for(i = 1 ; i <= 5 ; i++)
    {
        inicializar_combinatoria(&comb);
 
        combinaciones(&comb, 5 , i);
 
        for(j = 0 ; j < comb.n_elementos ; j++)
        {
            for(k = 0 ; k < comb.longitud_elemento ; k++)
                printf("%c",vocales[comb.lista[j][k]]);
            printf("\n");
        }
 
        finalizar_combinatoria(&comb);
    }
 
    return 0;
}
 

Había visto un error que no existia...  :P

¡Saludos!

Amchacon, lo he compilado sin modificar absolutamente nada. Do-while, ya sé que lo único que me hace falta es "jugar" con las posiciones de los elementos del array, pero  lo que no encuentro es el cómo combinarlos, es decir, un algoritmo que haga esas combinaciones sea cual sea el número de caracteres, y ahí es donde os pido ayuda.

Os pongo aquí parte del código que es donde tengo los problemas, este código es, de todos los que he probado hasta la fecha, el que mejor funciona posiblemente y el que es más sencillo de comprender porque es el más corto.


Gracias y saludos. :D
A ver si podéis orientarme un poco en el código este.