Algoritmo generazione UserID

MDS · Messaggio da **MDS** » sab 26 feb 2005, 9:56

Ciao a tutti.....
 Scrivo su questo forum, anche se non è una cosa legata a Linux, perchè ho trovato molte persone competenti e disponibili....
 Il mio problemino è trovare un algoritmo funzionale per la generazione di userid.
 Devo farlo in Java, ma anche se la vostra risposta fosse in C sarebbe mia cura capirla e tradurla.
 
 Allora questo algoritmo deve generare le combinazioni con le lettere del nome che immetto.
 Le regole sono e seguenti:
 1) La prima lettera del nome va conservata e quindi deve rimanere in prima posizione
 2) Devo arrivare fino a 4 caratteri di lungh max, però devo proporre prima le soluzioni + corte...
 
 Vi faccio un esempio.
 
 Se ho il nome Mario l´lagoritmo dovra produrre i seguenati risultati in quest´ordine
 
 Ma
 Mr
 Mi
 Mo
 
 Maa
 Mar
 Mai
 Mao
 
 Mra
 Mrr
 Mri
 Mro
 
 Mia
 Mir
 Mii
 Mio
 
 Moa
 Mor
 Moi
 Moo
 
 Maaa
 Maar
 Maai
 Maao
 
 Mara
 Marr
 Mari
 Maro
 
 E così via
 
 Vi viene in mente qualcosa?
 
 Grazie e ciao

mesillo · Messaggio da **mesillo** » gio 3 mar 2005, 13:48

Posso provare in c se vuoi... tieni conto che in questo linguaggio una stringa è un puntatore ed array di char.... questo può creare problemi nella "traduzione" in Java?
 P.S. se non si è capito di Java non sò un H!

mesillo · Messaggio da **mesillo** » gio 3 mar 2005, 16:09

non è mica un giochetto da ragazzi!!!... avevo sottovalutato il problema... comunque voglio provarci!

Sari · Messaggio da **Sari** » gio 3 mar 2005, 16:53

ci stro provando pure io da una buona mezz´ora (sembrava facile ma non lo è!).
 Ora pero´ il lavoro chiama

Cmqe secondo me l´idea di base e´ che ogni seguenza puo´ essere riportata facilmente ad un sistema di numerazione con base pari alla lunghezza della stringa - 1.
 La seguenza generata da una parola di 11 lettere seguirebbe una numerazione decimale avendo 10 elementi in gioco.
 Per comodita spiego con una parola di 4 lettere
 pane
 
 blocco A
 pa
 pn
 pe
 
 lettera 1
 paa
 pan
 pae
 
 lettera 2
 pna
 pnn
 pne
 
 lettera 3
 pea
 pen
 pee
 
 cioe´ tradotto tralasciando la "p" iniziale
 
 blocco A
 lettera 1 + blocco A
 lettera 2 + blocco A
 lettera 3 + blocco A
 
 se avessi una parola di 4 lettere potrei riassumere in
 
 blocco A
 
 lettera 1 + blocco A
 lettera 2 + blocco A
 lettera 3 + blocco A
 lettera 4 + blocco A
 
 lettera 1 + lettera 1 + blocco A
 lettera 1 + lettera 2 + blocco A
 ... eccetera fino a
 
 lettera 4 + lettera 1 + blocco A
 lettera 4 + lettera 2 + blocco A
 .... eccetera
 
 quindi riassumendo!
 
 A
 1A
 2A
 3A
 4A
 11A
 12A
 13A
 14A
 21A
 22A
 23A
 24A
 ... eccetera
 
 quindi come si puo´ notare e´ una numerazione di base 4
 la mia strada verteva nello sfruttare questo presupposto

Lo so lo so mi sono spiegato malissimo ghghgh

Sari · Messaggio da **Sari** » gio 3 mar 2005, 16:57

a gia lo sfruttavo utilizzando un vettore di interi, ogni intero stava ad indicare una lettera, e con una serie di cicli for costruivo la mia numerazione (visto che se ho in ingresso una stringa di 10000 elementi non posso contare su 10000 sinboli)

gianPrazio · Messaggio da **gianPrazio** » gio 3 mar 2005, 23:17

Il problema non e´ affatto banale! Se hai un nome di lunghezza N, hai bisogno, ti ritrovi con un numero di stringhe che alla fine e´ (N-1)! . Se poi li devi anche presentare in ordine in base alla posizione delle lettere, e´ un bel casino!

gianPrazio · Messaggio da **gianPrazio** » gio 3 mar 2005, 23:50

SCUSATEMI!!!! sono un imbecille patentato!!! ho giudicato la complessita´ dell´algoritmo solo dando un´occhiata di sfuggita al codice... in realta´ la complessita´ e´ O(n^2), dove n e´ la lunghezza del nome.
 Il programma e´ molto semplice: con un doppio ciclo for te la cavi senza problemi: eccoti il codice (non credo che in questo forum siano mantenute le tabulazioni, ma spero che sia ugualmente leggibile):
 
 
 <code>
 import java.io.*;
 
 public class CreateID
 {
 public static void main (String[] args)
 {
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 System.out.println("Immettere nome ...");
 String nome = "";
 try
 {
 nome = in.readLine();
 }
 catch (IOException e)
 {
 System.err.println(e);
 }
 System.out.println();
 for (int i = 0; i < nome.length(); i++)
 {
 String tmp = nome.substring(0, i + 1);
 for (int j = 1; j < nome.length(); j++)
 {
 tmp = tmp + nome.charAt(j);
 System.out.println(tmp);
 tmp = tmp.substring(0, tmp.length() - 1);
 }
 System.out.println();
 }
 }
 }
 </code>
 
 Salva il codice nel file CreateID.java, compilalo ed eseguilo. Con l´istanza "Mario" a me ha dato il seguente output:
 
 <code>
 Immettere nome ...
 Mario
 
 Ma
 Mr
 Mi
 Mo
 
 Maa
 Mar
 Mai
 Mao
 
 Mara
 Marr
 Mari
 Maro
 
 Maria
 Marir
 Marii
 Mario
 
 Marioa
 Marior
 Marioi
 Marioo
 
 
 </code>
 buonanotte!

mesillo · Messaggio da **mesillo** » ven 4 mar 2005, 16:41

Già!... anch´io ero arrivato a qualcosa di simile... ma se guardi il tuo output ti accorgerai che non è quello proposto da MSD.
 Il tuo, come il mio, mantiene sempre le prime lettere in ordine originale... ossia tu usi due indici/puntatori solo... insomma hai Mar ma non Mra in out... saltiamo delle possibilità di combinazione!
 Merrr... devo studiare lavorare... e non riesco a togliermi dalla testa stà roba!
 Aiuto!

gianPrazio · Messaggio da **gianPrazio** » ven 4 mar 2005, 18:13

Oh, giusto, hai ragione, mesillo!... non avevo letto bene... beh, dai, erano le 11 e mezza ieri sera :-] ...
 se ho un po´ di tempo ci penso su!

mesillo · Messaggio da **mesillo** » sab 5 mar 2005, 2:28

Tranqui!... anche io me ne sono accorto all´ultimo!... avremo tutti un qualcosa su cui pensare!
 
 Good Luk.

gianPrazio · Messaggio da **gianPrazio** » sab 5 mar 2005, 9:25

[Sara´ un po´ lunghetta...]
 Ciao! Allora... sono riuscito ad ottenere un codice che funziona (in certe condizioni)... il problema e´ che la soluzione e´ tutt´altro che banale, visto il numero di stringhe: se ho un nome in ingresso n caratteri, il numero di stringhe che posso ottenere di lunghezza 2 e´ n-1, quello di lunghezza 3 e´ (n-1)^2, quello di lunghezza 4 e´ (n-1)^3 (questo perche´ il primo carattere e´ sempre lo stesso). Il numero totale di stringhe e´ dunque (n-1) + (n-1)^2 + (n-1)^3 = (n-1) * [(n-1)^3 - 1] / (n-2) = O(n^3).... Con l´istanza "Mario", ad esempio, si ottengono 84 stringhe!!
 La mia soluzione (che non e´ per nulla efficiente) dapprima trova tutte le stringhe che possono essere generate e le va a mettere in un array di stringhe. Successivamente, le stampa tutte. Allora... il metodo per trovare le stringhe e´ il metodo ricorsivo computeID(); subito dopo aver ottenuto una stringa possibile, va a metterla nell´array nella posizione che si ottiene chiamando un altro metodo, computePos(). Il metodo computePos(), si crea un sistema di numerazione posizionale basato sulle posizioni dei caratteri del nome di ingresso ("Mario") e sulle posizioni dei caratteri della stringa che riceve in ingresso: trovata la giusta posizione dell´array, vi si mette la stringa generata.
 Quando si sono infilate tutte le stringhe nell´array, le si stampa tutte.
 Il codice e´ questo:
 
 <code>
 import java.io.*;
 
 public class CreateID
 {
 
 static String nome;
 static String[] array;
 
 public static void main (String[] args)
 {
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 System.out.println("Immettere nome ...");
 nome = "";
 try
 {
 nome = in.readLine();
 }
 catch (IOException e)
 {
 System.err.println(e);
 }
 int dimAr = (nome.length() - 1) * ((int)Math.pow(nome.length() - 1, 3) - 1) / (nome.length() - 2);
 array = new String[dimAr];
 System.out.println("numero stringe = " + dimAr);
 String str = "" + nome.charAt(0);
 System.out.println();
 computeID(str);
 for (int i = 0; i < array.length; i++)
 System.out.println(array);
 }
 
 static void computeID(String str)
 {
 if (str.length() == 4)
 return;
 for (int i = 1; i < nome.length(); i++)
 {
 str += nome.charAt(i);
 computeID(str);
 int pos = computePos(str);
 array[pos] = str;
 //System.out.println(str);
 str = str.substring(0, str.length() - 1);
 }
 }
 
 static int computePos(String str)
 {
 char[] pesi = new char[nome.length() - 1];
 for(int k = 1; k < nome.length(); k++)
 pesi[k - 1] = nome.charAt(k);
 int pos = 0;
 for (int i = str.length() - 1; i > 0; i--)
 {
 for (int j = 0; j < pesi.length; j++)
 {
 if (str.charAt(i) == pesi[j])
 {
 pos += (j+1)*(int)Math.pow(nome.length() - 1, str.length() - i - 1);
 break;
 }
 }
 }
 pos--;
 return pos;
 }
 }
 </code>
 L´output che mi da´ con input mario "Mario" e´:
 
 <code>
 filippo@baracca:~/univ$ java CreateID
 Immettere nome ...
 Mario
 numero stringe = 84
 
 Ma
 Mr
 Mi
 Mo
 Maa
 Mar
 Mai
 Mao
 Mra
 Mrr
 Mri
 Mro
 Mia
 Mir
 Mii
 Mio
 Moa
 Mor
 Moi
 Moo
 Maaa
 Maar
 Maai
 Maao
 Mara
 Marr
 Mari
 Maro
 Maia
 Mair
 Maii
 Maio
 Maoa
 Maor
 Maoi
 Maoo
 Mraa
 Mrar
 Mrai
 Mrao
 Mrra
 Mrrr
 Mrri
 Mrro
 Mria
 Mrir
 Mrii
 Mrio
 Mroa
 Mror
 Mroi
 Mroo
 Miaa
 Miar
 Miai
 Miao
 Mira
 Mirr
 Miri
 Miro
 Miia
 Miir
 Miii
 Miio
 Mioa
 Mior
 Mioi
 Mioo
 Moaa
 Moar
 Moai
 Moao
 Mora
 Morr
 Mori
 Moro
 Moia
 Moir
 Moii
 Moio
 Mooa
 Moor
 Mooi
 Mooo
 filippo@baracca:~/univ$
 </code>
 
 La computazione viene fatta correttamente, pero´ c´e´ un grave problema da risolvere: dato che il metodo computePos() si crea un sistema di numerazione posizionale tutto suo, se il nome di ingresso ha 2 o piu´ caratteri uguali in posizioni distinte (ad esempio: "Filippo" ha 2 ´p´ e 2 ´i´ in posizioni distinte), il programma non funziona correttamente...
 Un altro problema e´ quello legato all´efficienza: dato che il metodo computePos() richiede O(n^2) confronti tra caratteri, e dato che le stringhe sono O(n^3), il numero totale di confronti tra caratteri e´ O(n^5)!!!!!!
 
 Basta, mi fermo qua, dato che sono stato anche troppo prolisso e rompino...
 mesillo, se trovi una soluzione + efficiente e che riesca ad evitare il problema dei "caratteri uguali in posizioni diverse", fammi sapere!!
 ciauz!
 [ Questo Messaggio è stato Modificato da: gianPrazio il 05-03-2005 15:09 ]

rob · Messaggio da **rob** » sab 5 mar 2005, 11:52

aaaaaaa, stamattina mi sono svegliato con piglio polemico... preparatevi :-]
 dunque... inserimento ordinato di parole in una lista -> O(x²) (caso + brutto di così non si può, comunque si parla di upper bound), dove x è il numero di parole. ma poichè x = n³ -> complessità totale = O(n^6)... non vorrei sbagliarmi, ma gianprazio, xchè hai fatto n² · n³ ?
 e fino a qui siamo tristi... però:
 ho pensato che _forse_, nonstante la richiesta, non è che fosse proprio importante che l´output fosse ordinato alfabeticamente, _forse_ bastava ordinarlo solo per il numero di caratteri... in questo caso, dato che sono anche un po´ costruttivo, volevo proporre un metodo di inserimento nel vettore dei risultati = O( n )... seguimi gianpra

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Code:<HR></TD></TR><TR><TD><PRE>
 private void add( String toAdd ) {
 switch( toAdd.length() - 1 ) {
 case 1:
 out[ ind1++ ] = toAdd;
 break;
 case 2:
 out[ ind2++ ] = toAdd;
 break;
 case 3:
 out[ ind3++ ] = toAdd;
 break;
 default:
 System.out.println( "Che sto a fa´ qui???" );
 System.exit( 0 );
 }
 }
 
 private void setIndexes( String userID ) {
 length = userID.length() - 1;
 ind1 = 0;
 ind2 = length;
 ind3 = (int) Math.pow( length, 2 );
 length = (int) Math.pow( length, 3 ) + ind2 + ind3;
 }
 </PRE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 ho supposto che nella classe ci siano gli attributi length, ind1, ind2, ind3 settati da setIndexes non appena si conosce lo userID...
 inoltre appena trovo una nuova stringa, la passo al metodo add( String ) che me la mette al posto giusto nell´array dei risultati out.
 
 apertissimo a critiche :-]
 
 saluti, rob

gianPrazio · Messaggio da **gianPrazio** » sab 5 mar 2005, 12:15

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 05-03-2005 alle ore 11:52, rob :
 aaaaaaa, stamattina mi sono svegliato con piglio polemico... preparatevi :-]
 dunque... inserimento ordinato di parole in una lista -> O(x²) (caso + brutto di così non si può, comunque si parla di upper bound), dove x è il numero di parole. ma poichè x = n³ -> complessità totale = O(n^6)... non vorrei sbagliarmi, ma gianprazio, xchè hai fatto n² · n³ ?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ciao rob!
 ho fatto O(n^3 * n^2), perche´ le stringhe sono in tutto O(n^3)... la lunghezza di ciascuna stringa e´ O(n), e il numero di confronti tra caratteri che viene fatto PER CIASCUNA STRINGA e´ O(n^2)... per cui il numero totale di confronti si ottiene moltiplicando il numero totale di stringhe (che e´ O(n^3) ) per il numero di confronti necessario per 1 sola stringa (che e´ O(n^2) ): percio´ numero di confronti complessivo e´ O(n^3) * O(n^2) = O(n^3 * n^2) = O(n^5)...... tutto qua... non vedo perche´ debba essere O(n^6)...
 Comunque... effettivamente, dalle richieste di MDS, sembra che le stringhe vadano ordinate solo in base alla loro lunghezza (non e´ stato specificato che dovessero essere ordinate anche in base all´ordine con cui compaiono i caratteri nel nome di ingresso)... in questo caso, usando il tuo metodo, di confronti tra caratteri non ce ne sono e percio´ per il "modello di costo" bisogna considerare il numero di operazioni fatto per inserire nell´array ogni stringa: dato che sono necessarie O(1) istruzioni (per ogni stringa) per trovare la posizione giusta nell´array di stringhe (dato che si incrementa 1 solo indice per ogni stringa, nel tuo metodo add(String) ), e dato che il numero di stringhe e´ O(n^3), il numero totale di operazioni e´ O(n^3) * O(1) = O(n^3), di molto inferiore a O(n^5)...
 il fatto e´ che io mi ero basato sull´esempio dato da MDS con la stringa "Mario", per cui credevo che di dovesse tenere conto, per l´ordine con cui venivano sparate in output le stringhe, anche dell´ordine in base al quale erano disposti i caratteri delle stringhe in uscita.
 Fammi sapere :-]

rob · Messaggio da **rob** » sab 5 mar 2005, 12:40

ok, ho capito il mio errore: sto facendo un gran casino a usare n, una volta l´ho usato per il numero di caratteri, una volta per il numero di parole... e meno male che avevo pure usato x per evitare st´errore!... ci ho riflettuto e a un certo punto ho visto la luce :-] decisamente giusto il tuo O( n^5 )
 fico però l´algoritmo O( 1 ), eh? :-P
 
 buona giornata :-]
 rob

gianPrazio · Messaggio da **gianPrazio** » sab 5 mar 2005, 13:05

Gia´, fichissimo! :-] :-] :-]
 
 Buon fine settimana anche a te!