Repository 32bit  Forum
Repository 64bit  Wiki

Algoritmo generazione UserID

Area di discussione libera.

Moderatore: Staff

Regole del forum
1) Rispettare le idee altrui.
2) Evitare le offese dirette.
3) Leggere attentamente le risposte ricevute
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

Algoritmo generazione UserID

Messaggioda MDS » sab feb 26, 2005 9:56

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

Algoritmo generazione UserID

Messaggioda mesillo » gio mar 03, 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? <BR>P.S. se non si è capito di Java non sò un H!<br>
mesillo
Linux 2.0
Linux 2.0
 
Messaggi: 169
Iscritto il: ven feb 04, 2005 0:00
Località: Adria (RO)

Algoritmo generazione UserID

Messaggioda mesillo » gio mar 03, 2005 16:09

non è mica un giochetto da ragazzi!!!... avevo sottovalutato il problema... comunque voglio provarci!<br>
mesillo
Linux 2.0
Linux 2.0
 
Messaggi: 169
Iscritto il: ven feb 04, 2005 0:00
Località: Adria (RO)

Algoritmo generazione UserID

Messaggioda Sari » gio mar 03, 2005 16:53

ci stro provando pure io da una buona mezz´ora (sembrava facile ma non lo è!). <BR>Ora pero´ il lavoro chiama :( <BR> <BR>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. <BR>La seguenza generata da una parola di 11 lettere seguirebbe una numerazione decimale avendo 10 elementi in gioco. <BR>Per comodita spiego con una parola di 4 lettere <BR>pane <BR> <BR>blocco A <BR>pa <BR>pn <BR>pe <BR> <BR>lettera 1 <BR>paa <BR>pan <BR>pae <BR> <BR>lettera 2 <BR>pna <BR>pnn <BR>pne <BR> <BR>lettera 3 <BR>pea <BR>pen <BR>pee <BR> <BR>cioe´ tradotto tralasciando la "p" iniziale <BR> <BR>blocco A <BR>lettera 1 + blocco A <BR>lettera 2 + blocco A <BR>lettera 3 + blocco A <BR> <BR>se avessi una parola di 4 lettere potrei riassumere in <BR> <BR>blocco A <BR> <BR>lettera 1 + blocco A <BR>lettera 2 + blocco A <BR>lettera 3 + blocco A <BR>lettera 4 + blocco A <BR> <BR>lettera 1 + lettera 1 + blocco A <BR>lettera 1 + lettera 2 + blocco A <BR>... eccetera fino a <BR> <BR>lettera 4 + lettera 1 + blocco A <BR>lettera 4 + lettera 2 + blocco A <BR>.... eccetera <BR> <BR>quindi riassumendo! <BR> <BR>A <BR>1A <BR>2A <BR>3A <BR>4A <BR>11A <BR>12A <BR>13A <BR>14A <BR>21A <BR>22A <BR>23A <BR>24A <BR>... eccetera <BR> <BR>quindi come si puo´ notare e´ una numerazione di base 4 <BR>la mia strada verteva nello sfruttare questo presupposto :) <BR>Lo so lo so mi sono spiegato malissimo ghghgh <BR><br>
Avatar utente
Sari
Linux 2.6
Linux 2.6
 
Messaggi: 584
Iscritto il: mer feb 16, 2005 0:00
Località: Verona
Slackware: 12.1
Kernel: 2.6.24
Desktop: Gnome

Algoritmo generazione UserID

Messaggioda Sari » gio mar 03, 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) <BR><br>
Avatar utente
Sari
Linux 2.6
Linux 2.6
 
Messaggi: 584
Iscritto il: mer feb 16, 2005 0:00
Località: Verona
Slackware: 12.1
Kernel: 2.6.24
Desktop: Gnome

Algoritmo generazione UserID

Messaggioda gianPrazio » gio mar 03, 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!<br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Algoritmo generazione UserID

Messaggioda gianPrazio » gio mar 03, 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. <BR>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): <BR> <BR> <BR><code> <BR>import java.io.*; <BR> <BR>public class CreateID <BR>{ <BR> public static void main (String[] args) <BR> { <BR> BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); <BR> System.out.println("Immettere nome ..."); <BR> String nome = ""; <BR> try <BR> { <BR> nome = in.readLine(); <BR> } <BR> catch (IOException e) <BR> { <BR> System.err.println(e); <BR> } <BR> System.out.println(); <BR> for (int i = 0; i < nome.length(); i++) <BR> { <BR> String tmp = nome.substring(0, i + 1); <BR> for (int j = 1; j < nome.length(); j++) <BR> { <BR> tmp = tmp + nome.charAt(j); <BR> System.out.println(tmp); <BR> tmp = tmp.substring(0, tmp.length() - 1); <BR> } <BR> System.out.println(); <BR> } <BR> } <BR>} <BR></code> <BR> <BR>Salva il codice nel file CreateID.java, compilalo ed eseguilo. Con l´istanza "Mario" a me ha dato il seguente output: <BR> <BR><code> <BR>Immettere nome ... <BR>Mario <BR> <BR>Ma <BR>Mr <BR>Mi <BR>Mo <BR> <BR>Maa <BR>Mar <BR>Mai <BR>Mao <BR> <BR>Mara <BR>Marr <BR>Mari <BR>Maro <BR> <BR>Maria <BR>Marir <BR>Marii <BR>Mario <BR> <BR>Marioa <BR>Marior <BR>Marioi <BR>Marioo <BR> <BR> <BR></code> <BR>buonanotte!<br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Algoritmo generazione UserID

Messaggioda mesillo » ven mar 04, 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. <BR>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! <BR>Merrr... devo studiare lavorare... e non riesco a togliermi dalla testa stà roba! <BR>Aiuto!<br>
mesillo
Linux 2.0
Linux 2.0
 
Messaggi: 169
Iscritto il: ven feb 04, 2005 0:00
Località: Adria (RO)

Algoritmo generazione UserID

Messaggioda gianPrazio » ven mar 04, 2005 18:13

Oh, giusto, hai ragione, mesillo!... non avevo letto bene... beh, dai, erano le 11 e mezza ieri sera :-] ... <BR>se ho un po´ di tempo ci penso su!<br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Algoritmo generazione UserID

Messaggioda mesillo » sab mar 05, 2005 2:28

Tranqui!... anche io me ne sono accorto all´ultimo!... avremo tutti un qualcosa su cui pensare! <BR> <BR>Good Luk. :-) <br>
mesillo
Linux 2.0
Linux 2.0
 
Messaggi: 169
Iscritto il: ven feb 04, 2005 0:00
Località: Adria (RO)

Algoritmo generazione UserID

Messaggioda gianPrazio » sab mar 05, 2005 9:25

[Sara´ un po´ lunghetta...] <BR>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!! <BR>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. <BR>Quando si sono infilate tutte le stringhe nell´array, le si stampa tutte. <BR>Il codice e´ questo: <BR> <BR><code> <BR>import java.io.*; <BR> <BR>public class CreateID <BR>{ <BR> <BR> static String nome; <BR> static String[] array; <BR> <BR> public static void main (String[] args) <BR> { <BR> BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); <BR> System.out.println("Immettere nome ..."); <BR> nome = ""; <BR> try <BR> { <BR> nome = in.readLine(); <BR> } <BR> catch (IOException e) <BR> { <BR> System.err.println(e); <BR> } <BR> int dimAr = (nome.length() - 1) * ((int)Math.pow(nome.length() - 1, 3) - 1) / (nome.length() - 2); <BR> array = new String[dimAr]; <BR> System.out.println("numero stringe = " + dimAr); <BR> String str = "" + nome.charAt(0); <BR> System.out.println(); <BR> computeID(str); <BR> for (int i = 0; i < array.length; i++) <BR> System.out.println(array[i]); <BR> } <BR> <BR> static void computeID(String str) <BR> { <BR> if (str.length() == 4) <BR> return; <BR> for (int i = 1; i < nome.length(); i++) <BR> { <BR> str += nome.charAt(i); <BR> computeID(str); <BR> int pos = computePos(str); <BR> array[pos] = str; <BR> //System.out.println(str); <BR> str = str.substring(0, str.length() - 1); <BR> } <BR> } <BR> <BR> static int computePos(String str) <BR> { <BR> char[] pesi = new char[nome.length() - 1]; <BR> for(int k = 1; k < nome.length(); k++) <BR> pesi[k - 1] = nome.charAt(k); <BR> int pos = 0; <BR> for (int i = str.length() - 1; i > 0; i--) <BR> { <BR> for (int j = 0; j < pesi.length; j++) <BR> { <BR> if (str.charAt(i) == pesi[j]) <BR> { <BR> pos += (j+1)*(int)Math.pow(nome.length() - 1, str.length() - i - 1); <BR> break; <BR> } <BR> } <BR> } <BR> pos--; <BR> return pos; <BR> } <BR>} <BR></code> <BR>L´output che mi da´ con input mario "Mario" e´: <BR> <BR><code> <BR>filippo@baracca:~/univ$ java CreateID <BR>Immettere nome ... <BR>Mario <BR>numero stringe = 84 <BR> <BR>Ma <BR>Mr <BR>Mi <BR>Mo <BR>Maa <BR>Mar <BR>Mai <BR>Mao <BR>Mra <BR>Mrr <BR>Mri <BR>Mro <BR>Mia <BR>Mir <BR>Mii <BR>Mio <BR>Moa <BR>Mor <BR>Moi <BR>Moo <BR>Maaa <BR>Maar <BR>Maai <BR>Maao <BR>Mara <BR>Marr <BR>Mari <BR>Maro <BR>Maia <BR>Mair <BR>Maii <BR>Maio <BR>Maoa <BR>Maor <BR>Maoi <BR>Maoo <BR>Mraa <BR>Mrar <BR>Mrai <BR>Mrao <BR>Mrra <BR>Mrrr <BR>Mrri <BR>Mrro <BR>Mria <BR>Mrir <BR>Mrii <BR>Mrio <BR>Mroa <BR>Mror <BR>Mroi <BR>Mroo <BR>Miaa <BR>Miar <BR>Miai <BR>Miao <BR>Mira <BR>Mirr <BR>Miri <BR>Miro <BR>Miia <BR>Miir <BR>Miii <BR>Miio <BR>Mioa <BR>Mior <BR>Mioi <BR>Mioo <BR>Moaa <BR>Moar <BR>Moai <BR>Moao <BR>Mora <BR>Morr <BR>Mori <BR>Moro <BR>Moia <BR>Moir <BR>Moii <BR>Moio <BR>Mooa <BR>Moor <BR>Mooi <BR>Mooo <BR>filippo@baracca:~/univ$ <BR></code> <BR> <BR>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... <BR>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)!!!!!! <BR> <BR>Basta, mi fermo qua, dato che sono stato anche troppo prolisso e rompino... <BR>mesillo, se trovi una soluzione + efficiente e che riesca ad evitare il problema dei "caratteri uguali in posizioni diverse", fammi sapere!! <BR>ciauz! ;-) <BR><BR><BR>[ Questo Messaggio è stato Modificato da: gianPrazio il 05-03-2005 15:09 ]<br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Algoritmo generazione UserID

Messaggioda rob » sab mar 05, 2005 11:52

aaaaaaa, stamattina mi sono svegliato con piglio polemico... preparatevi :-] <BR>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³ ? <BR>e fino a qui siamo tristi... però: <BR>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 :-D <BR> <BR><!-- BBCode Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Code:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><PRE> <BR>private void add( String toAdd ) { <BR> switch( toAdd.length() - 1 ) { <BR> case 1: <BR> out[ ind1++ ] = toAdd; <BR> break; <BR> case 2: <BR> out[ ind2++ ] = toAdd; <BR> break; <BR> case 3: <BR> out[ ind3++ ] = toAdd; <BR> break; <BR> default: <BR> System.out.println( "Che sto a fa´ qui???" ); <BR> System.exit( 0 ); <BR> } <BR>} <BR> <BR>private void setIndexes( String userID ) { <BR> length = userID.length() - 1; <BR> ind1 = 0; <BR> ind2 = length; <BR> ind3 = (int) Math.pow( length, 2 ); <BR> length = (int) Math.pow( length, 3 ) + ind2 + ind3; <BR>} <BR></PRE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode End --> <BR> <BR>ho supposto che nella classe ci siano gli attributi length, ind1, ind2, ind3 settati da setIndexes non appena si conosce lo userID... <BR>inoltre appena trovo una nuova stringa, la passo al metodo add( String ) che me la mette al posto giusto nell´array dei risultati out. <BR> <BR>apertissimo a critiche :-] <BR> <BR>saluti, rob<br>
Avatar utente
rob
Linux 2.6
Linux 2.6
 
Messaggi: 924
Iscritto il: lun nov 22, 2004 0:00
Località: Roma

Algoritmo generazione UserID

Messaggioda gianPrazio » sab mar 05, 2005 12:15

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE> <BR> 05-03-2005 alle ore 11:52, rob : <BR>aaaaaaa, stamattina mi sono svegliato con piglio polemico... preparatevi :-] <BR>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³ ? <BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End --> <BR> <BR>Ciao rob! <BR>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)... <BR>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)... <BR>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. <BR>Fammi sapere :-] <br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Algoritmo generazione UserID

Messaggioda rob » sab mar 05, 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 ) <BR>fico però l´algoritmo O( 1 ), eh? :-P <BR> <BR>buona giornata :-] <BR>rob<br>
Avatar utente
rob
Linux 2.6
Linux 2.6
 
Messaggi: 924
Iscritto il: lun nov 22, 2004 0:00
Località: Roma

Algoritmo generazione UserID

Messaggioda gianPrazio » sab mar 05, 2005 13:05

Gia´, fichissimo! :-] :-] :-] <BR> <BR>Buon fine settimana anche a te! ;-) <br>
gianPrazio
Linux 2.4
Linux 2.4
 
Messaggi: 388
Iscritto il: mar set 28, 2004 23:00
Località: Castelfranco Veneto

Prossimo

Torna a Libera

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti