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.
Cita de: goto C en 28 Julio 2013, 21:02 PM
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...
Cita de: goto C en 28 Julio 2013, 21:46 PM
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?
Citara.c:80:25: warning: assignment discards 'const' qualifier from pointer target ty
pe [enabled by default]
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.
Cita de: goto C en 28 Julio 2013, 22:39 PM
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.
¿Has probado el código literalmente o has hecho algun cambio?
Cita de: goto C en 28 Julio 2013, 22:39 PMEDITO 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.
;)
¡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.
#include<stdio.h>
#include<stdlib.h>
int main()
{
int numcarac, auxnumcarac, i, j, k, l=0, contador=1; //numcarac es el numero de caracteres del array carac y auxnumcarac el de caraccomb
char carac[26], caraccomb[26]; //carac es el array con todos los caracteres, y caraccomb el array en el que iremos guardando las diferentes combinaciones de los caracteres de carac
//... pedimos datos por teclado, los guardamos y los mostramos para asegurarnos, esto funciona bien, comprobado, no lo pongo para no liar mas
//AQUI ESTA EL PROBLEMA:
auxnumcarac=2;
for(i=0; i<numcarac; i++)
{
for(j=i; j<numcarac; j++)
{
for(k=0; k<auxnumcarac; k++)
{
caraccomb[l] = carac[j+k];
l++;
}
//aqui mostramos caraccomb:
printf("%s\n", caraccomb);
}
auxnumcarac++;
l=0;
}
Gracias y saludos. :D
A ver si podéis orientarme un poco en el código este.