[C] Generatore di stringhe

[/dev/null]

Dovrei fare un programma in grado di generare stringhe...
Dovrebbe cioe' generare tutte le stringhe possibili da 1 carattere a X caratteri...

Eccovi l'esempietto:
a
b
c
d
...
y
z
aa
ab
ac
...
az
ba
bb
...
zy
zz
aaa
aab
...
aaz
aba
...
azz
baa
...
zzz
aaaa
...


Etc etc... Capito?


Non riesco a realizzare un algoritmo che lo faccia in maniera "dinamica"...
A voi viene in mente una soluzione?

[anx721]

Per avere una soluzione dinamica devi usare la ricorsione o simulare la ricorsione con uno stack. Io ti propongo una soluzione ricorsiva basata sulla seguente osservazione:

per stampare tutte le parole di lunghezza n posso stampare tutte le parole di lunghezza n-1 precedute dal carattere 'a', poi le ristampo precedute dal carattere 'b', e cosi via... L'idea è quindi di accumulare la parola carattere dopo carattere in un array word attraverso le varie chiamate ricorsive; len rapresneta la lunghezza della parola che resta da generare mentre currente è la posizione in cui scrivere il carattere corrente:

Nell'esempio uso solo le lettere da 'a' ad 'e' e genero tutte le parole di lunghezza 3 perke se no sono troppeeeee:

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

void genera(char word[], int len, int current){
	if(len == 0){
		word[current] = '\0';
		printf("\n%s", word);
		return;
	}
	for(char c = 'a'; c <= 'e'; c++){
		word[current] = c;
		genera(word, len - 1, current + 1);
	}
}

int main(){
	int len = 3;
	char *word = (char *)malloc(len + 1 * sizeof(char));
	genera(word, len, 0);
	free(word);
}

genera(word, len, 0);

stampa tutte le parole di lunghezza n; a questo punto ti basta richiamare genera(word, i, 0); facendo variare i da 0 a len,

[/dev/null]

E io che mi ci stavo scervellando da un paio di giorni VVoVe:
Grazie






PS: Per caso e' possibile riscriverlo senza utilizzare la ricorsione? Suppongo di si'... Ma come?
Domani ci ragionero' un altro po'

[FreeManX]

non ho voglia di scrivere il codice corretto di to l'idea

ti crei un array con i caratteri con cui vuoi che si componga la parola, dopodiche fai un ciclo di lunghezza pari a quella che vuoi abbia la parola, e li genere una serie di numeri casuali compresi entro la lunghezza dell'array caratteri, cosi ti generi la parola in automatico.

anzi lo scritto il codice, pero non ho controllato se abbia errori, perche sono senza compilatore:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN_WORD 5

int main(int argc, char** argv) {
 char lista_char[] = {'a','b','c','d','e','f','g','h'};
 char word[LEN_WORD+1]
 int i=0;

 for (i=0; i <= LEN_WORD, i++) {
   srand( (unsigned int)time( NULL ) );
   int r = rand() % i;
   word[i]=lista_char[r];

 } 
 lista_char[LEN_WORD+1]='\0';
 
 prinf("Stringa: %s\n",word);



}

[edriv]

Questo è un mio programma completo che fa quello che vuoi tu:
(non è ricorsivo)
La funzione + importante è disp()

#include <iostream>
#include <string>
// per system("PAUSE") e exit()
#include <cstdlib>

using namespace std;

void disp();
void init();
void show();
void filltable();

int tot_chars;
int *vals;
string parola;

int main()
{
    // Spiege come formattare l'input
	cout << "Inserisci una parola che contenga tutte le lettere da utilizzare e premi invio." << endl;
	cout << "Scrivi 'alfa' se vui tutto l'alfabeto minuscolo." << endl;
	cout << "Scrivi 'ALFA' se vui tutto l'alfabeto maiuscolo." << endl;
	cout << "Scrivi 'Alfa' se vui tutto l'alfabeto minuscolo e maiuscolo." << endl;
	cout << "Permi solo invio per le cifre da 0 a 9." << endl;
	// 40 caratteri dovrebbero bastare a fondere qualsiasi computer
	char buf[40];
	// Qui chiede l'input con getline()
 	cin.getline(buf,40); parola = buf;
 	// Riempie la tabella dei caratteri (se ad esempio ha messo "Alfa"
	filltable();
	cout << "Quanto sarà lunga ogni combinazione?" << endl;
	do {
	    cin >> tot_chars;
	} while(tot_chars <= 0);    
	// Crea l'array delle combinazioni
	vals = new int[tot_chars];
	if(!vals)
	{
		cout << "Memoria insufficiente!!!"<<endl;
		system("PAUSE");
		exit(1);
	}
	// Inizializza con il primo valore
	init();
	// Mostra tutte le combinazioni
	disp();
	// Cancella l'array delle combinazioni
	delete [] vals;
	cout << "Grazie e arrivederci." << endl;
	system("PAUSE");
	return 0;
}

void filltable()
{
	int i;
	if(parola == "alfa")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'a' a 'z'
		for(i='a'; i<='z'; i++)
			parola += i;
	}			
	else if(parola == "ALFA")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'A' a 'Z'
		for(i='A'; i<='Z'; i++)
			parola += i;
	}	
	else if(parola == "Alfa")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'a' a 'z'
		for(i='a'; i<='z'; i++)
			parola += i;
		// Riempie la tabella con lettere da 'A' a 'Z'
		for(i='A'; i<='Z'; i++)
			parola += i;
	}
	else if(parola.size() == 0)
	{
	    parola = "";
		// Riempie la tabella con cifre da '0' a '9'
		for(i='0'; i<='9'; i++)
			parola += i;
	}
}

void disp()
{
	int last = tot_chars - 1;
	int pos = last;
	bool end_flag;

	// Mostra la combinazione attuale (tutti zeri)
	show();
	for(end_flag = false; !end_flag; )
	{
		// Incrementa il valore alla posizione corrente
		vals[pos]++;
		// Mostra la combinazione attuale
		show();
		// Torna alla prima posizione.
		pos = last;
		// Vado avanti finchè non trovo un valore che non sia l'ultimo
		while (vals[pos]==(parola.size()-1))
		{
			// Imposto la posizione corrente a 0
			vals[pos] = 0;
			// precedente
			pos--;
			// Se sono arrivato prima dell'inizio del vettore, 
			// cioè anche il primo carattere era un valore finale (come 9)
			// allora ho finito.
			if(pos < 0) end_flag = true;
		}

	}
}

void show()
{
	for(int i=0; i<tot_chars; i++)
	{
		cout << parola[vals[i]];
	}
	cout << endl;
}

void init()
{
    for(int i=0; i<tot_chars; i++)
    	vals[i] = 0;	

}

Se trovi bug avvisami!

[RaouL_BennetH]

Originariamente inviato da edriv
Questo è un mio programma completo che fa quello che vuoi tu:
(non è ricorsivo)
La funzione + importante è disp()

#include <iostream>
#include <string>
// per system("PAUSE") e exit()
#include <cstdlib>

using namespace std;

void disp();
void init();
void show();
void filltable();

int tot_chars;
int *vals;
string parola;

int main()
{
    // Spiege come formattare l'input
	cout << "Inserisci una parola che contenga tutte le lettere da utilizzare e premi invio." << endl;
	cout << "Scrivi 'alfa' se vui tutto l'alfabeto minuscolo." << endl;
	cout << "Scrivi 'ALFA' se vui tutto l'alfabeto maiuscolo." << endl;
	cout << "Scrivi 'Alfa' se vui tutto l'alfabeto minuscolo e maiuscolo." << endl;
	cout << "Permi solo invio per le cifre da 0 a 9." << endl;
	// 40 caratteri dovrebbero bastare a fondere qualsiasi computer
	char buf[40];
	// Qui chiede l'input con getline()
 	cin.getline(buf,40); parola = buf;
 	// Riempie la tabella dei caratteri (se ad esempio ha messo "Alfa"
	filltable();
	cout << "Quanto sarà lunga ogni combinazione?" << endl;
	do {
	    cin >> tot_chars;
	} while(tot_chars <= 0);    
	// Crea l'array delle combinazioni
	vals = new int[tot_chars];
	if(!vals)
	{
		cout << "Memoria insufficiente!!!"<<endl;
		system("PAUSE");
		exit(1);
	}
	// Inizializza con il primo valore
	init();
	// Mostra tutte le combinazioni
	disp();
	// Cancella l'array delle combinazioni
	delete [] vals;
	cout << "Grazie e arrivederci." << endl;
	system("PAUSE");
	return 0;
}

void filltable()
{
	int i;
	if(parola == "alfa")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'a' a 'z'
		for(i='a'; i<='z'; i++)
			parola += i;
	}			
	else if(parola == "ALFA")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'A' a 'Z'
		for(i='A'; i<='Z'; i++)
			parola += i;
	}	
	else if(parola == "Alfa")
	{
	    parola = "";
		// Riempie la tabella con lettere da 'a' a 'z'
		for(i='a'; i<='z'; i++)
			parola += i;
		// Riempie la tabella con lettere da 'A' a 'Z'
		for(i='A'; i<='Z'; i++)
			parola += i;
	}
	else if(parola.size() == 0)
	{
	    parola = "";
		// Riempie la tabella con cifre da '0' a '9'
		for(i='0'; i<='9'; i++)
			parola += i;
	}
}

void disp()
{
	int last = tot_chars - 1;
	int pos = last;
	bool end_flag;

	// Mostra la combinazione attuale (tutti zeri)
	show();
	for(end_flag = false; !end_flag; )
	{
		// Incrementa il valore alla posizione corrente
		vals[pos]++;
		// Mostra la combinazione attuale
		show();
		// Torna alla prima posizione.
		pos = last;
		// Vado avanti finchè non trovo un valore che non sia l'ultimo
		while (vals[pos]==(parola.size()-1))
		{
			// Imposto la posizione corrente a 0
			vals[pos] = 0;
			// precedente
			pos--;
			// Se sono arrivato prima dell'inizio del vettore, 
			// cioè anche il primo carattere era un valore finale (come 9)
			// allora ho finito.
			if(pos < 0) end_flag = true;
		}

	}
}

void show()
{
	for(int i=0; i<tot_chars; i++)
	{
		cout << parola[vals[i]];
	}
	cout << endl;
}

void init()
{
    for(int i=0; i<tot_chars; i++)
    	vals[i] = 0;	

}

Se trovi bug avvisami!

scusa, ma questo non è C++ ?

[edriv]

Sì, ho letto male: è C++ ma facilmente adattabile, l'importante è l'algoritmo (poi basta sostituire l'I/O ... )

P.S. Se riesci a modificare il tuo messaggio visto che hai quotato tutto il codica...