[C++ o Java] Generazione di stringhe (combinazioni)

[SkOrPiOn`87]

Ciao,

Sono ormai molti giorni che mi sto spappolando il cervello al tentativo di costruire una funzione che data una stringa di N numeri da >0 anche (50 caratteri o +), mi restituisca tutte le combinazioni possibili di frasi...

Qualcuno di voi ci ha mai provato? non sono ancora riuscito a trovare un algoritmo comune per tutti...

[SkOrPiOn`87]

L'unico algoritmo migliore che ho potuto trovare è che se prendiamo una parola di 3 lettere e prendiamo l'ultima lettera e la spostiamo verso sinistra fino ad arrivare al primo posto e ripetiamo il meccanismo con tutte le lettere finchè non troviamo la frase di partenza abbiamo ottenuto tutte le combinazioni possibili...

Adesso io avevo pensato nel caso ci fossero piu di 3 lettere di dividere la frase in pezzi di 5 4 o 3 in modo da poter far funziona questo algoritmon in qualsiasi modo, infatti una frase di 12 caratteri può essere divisa in 3 pezzi da 4... ecc. Ecciziona fatta per i numeri primi che che hanno bisogno di un algoritmo pensato esclcusivamente per loro....

Ho allegato un'immagine dello schema che ho fatto per testare la logica del programma (spero vi sia chiaro...)

In poche parole se la frase è composta da 5 lettere, noi prendiamo le ultime e ne otteniamo tutte le combinazioni come descritto in precedenza, dopo invece scambiamo le 2 lettere (le prime due rimaste escluse, come da disegno allegato) con le altre lettere.... tutto questo fino ad ottenere la frase di 5 lettere da cui siamo partite... (guardando l'immagine si può capire meglio)....

www.studentimarconi.com/anagramma.JPG
A causa delle dimensioni dell'immagini alleggo in quel link l'immagine, purtroppo non ho strumenti di ritocco per poterla dimunuire di peso.....

Ciao

[pprllo]

Cioè, ti serve un programma che faccia tutte gli anagrammi possibili di una parola di N caratteri ?
Per esempio con ciao ti tira fuori:
ciao
cioa
coia
coai
caio
caoi
ecc...
ecc...
???

[SkOrPiOn`87]

si, proprio questo

[pprllo]

Guarda, io ho scritto un programma che lo fa, solo che al momento non ho i sorgenti. Mi serve un pò per recuperarli. Comunque tieni presente che il numero di combinazioni è ENORME. Per un numero N di caratteri, le combinazioni sono N!, quindi se metti parole di più di 11-12 caratteri per generare tutte le combinazioni ci vuole un tempo ENORME.

[LeleFT]

Originariamente inviato da pprllo
Guarda, io ho scritto un programma che lo fa, solo che al momento non ho i sorgenti. Mi serve un pò per recuperarli. Comunque tieni presente che il numero di combinazioni è ENORME. Per un numero N di caratteri, le combinazioni sono N!, quindi se metti parole di più di 11-12 caratteri per generare tutte le combinazioni ci vuole un tempo ENORME.

Questo è in parte vero: sono un po' meno di n! dato che alcune lettere possono essere ripetute. (Esempio, la parola BAIA non ha 24 possibili anagrammi, ma ne ha meno, perchè posso invertire le due A, senza alterare la parola in tutti i suoi anagrammi).
In totale dovrebbero essere n!/(n-k)! dove k è il numero di elementi uguali.


Ciao.

[pprllo]

Si, ma non conosco un modod per evitare i duplicati. Quindi di fatto il computer nel calcola N! con il mio sistema, che vado ora a scrivere:

#include <string>
#include <iostream>
using namespace std;

void Anagramma(string A, string B)
{
	if (A.size() == 0) cout << B << endl;
	else
	for (int i = 0; i < A.size(); i++)
	{
		char temp[2];
		temp[0] = A[i]; temp[1] = '\0';
		A.erase(i, 1);
		Anagramma(A, B + temp);
		A.insert(i, temp);	
	}
}
int main()
{
	string A;
	cin >> A;
	cout << endl;
	Anagramma(A, "");
}

Questa è una funzione ricorsiva. Scrivi la stringa in input e il programma farà tutti gli anagrammi. Tuttavia siccome non ricordavo il codice originale l'ho riscritto e non so se è esatto. Però ho provato con "tre" e "ciao" e "prova" e ha funzionato.

[pprllo]

#include <string>
#include <iostream>
using namespace std;

void Anagramma(string A, string B)
{
	if (A.size() == 0) cout << B << endl;
	else
	{
		string Doppie;
		for (int i = 0; i < A.size(); i++)
		{
			char temp[2];
			temp[0] = A[i]; temp[1] = '\0';
			if (Doppie.find(temp, 0) == string::npos)
			{
				A.erase(i, 1);
				Anagramma(A, B + temp);
				Doppie += temp;
				A.insert(i, temp);
			}
		}
	}
}
int main()
{
	string A;
	cin >> A;
	cout << endl;
	Anagramma(A, "");
}

MAGIA !!! Incoraggiato da Lele ho cercato di migliorare il programma ! Ora questo qui dovrebbe evitare i doppioni.

[SkOrPiOn`87]

Maledette ricorsi, ci avevo pensatoa nche io ad usarle per questo programma, ma purtroppo mi restano semrpe difficili da usare ghghghghg

[Birbun]

Domanda da neofita del C++: l'else non potrebbe essere trascurato visto che la condizione su A.size è esclusiva? :master: