n° 219
Novembre 2017
Dicembre 11, 2017, 04:15:40 *
Benvenuto! Accedi o registrati.
Hai dimenticato l'e-mail di attivazione?

Accesso con nome utente, password e durata della sessione
Notizia:
 
   Indice   Linux Windows Techassistance Gameassistance videogame hardware Aiuto Ricerca Agenda Downloads Accedi Registrati  


* Messaggi recenti
Messaggi recenti
Pagine: [1]   Vai giù
  Stampa  
Autore Discussione: Generazione di stringhe alfanumeriche composte sequenziali e non ripetute  (Letto 2858 volte)
0 utenti e 1 Utente non registrato stanno visualizzando questa discussione.
noob.81
Newbie
*

Karma: +0/-0
Scollegato Scollegato

Messaggi: 3


Mostra profilo E-mail
« inserita:: Gennaio 29, 2016, 12:05:45 »

Devo generare delle stringhe alfabetiche di tre caratteri formati dalla combinazione di questi caratteri tipo:
AAA
AAB
AAC
....
ZZX
ZZY
ZZZ

E devo generare in concatenazione altre stringhe formate da un carattere alfabetico e due numerici che se minori di 10 devono iniziare con lo 0 le quali verranno separate da un trattino.

nella fattispecie mi serve un output del tipo:
xxx-yzz
- dove con xxx intendo il set di caratteri sopra citati
- il trattino deve rimanere tale
- la y rappresenta una lettera dell'alfabeto dalla a alla z
- la zz rappresenta un numero che parte da 01 e finisce a 99

es. output
brc-d04.stringa_generica

La generazione dovrebbe essere incrementale e sequenziale quindi fornirmi tanti output quante sono le combinazioni possibili.

Le stringhe devono essere generate interamente, una dopo l'altra già finite affinchè queste possano essere successivamente memorizzate in una variabile il cui valore deve subire controlli successivi prima di essere stampato (per i controlli non ci sono problemi so come fare).

La mia difficoltà sta nel fatto che la stringa è composta.

Un codice di questo tipo:
Codice:
<?php
$maxLength 
3;
$charSet 'abcdefgjhklmnopqrstuvwxyz';
$size strlen($charSet);
$base = array();
$counter 0;
$baseSize 3;
// Let's see how many combinations exist for the given length and charset
$combinations 0;
for(
$i=1;$i<=$maxLength;$i++) {
$combinations += pow($size,$i);

echo 
"There are $combinations possible combinations!<br/><br/>";
while(
$baseSize <= $maxLength) {
// Go through all the possible combinations of last character and output $base
for($i=0;$i<$size;$i++) {
$base[0] = $i;
for($j=$baseSize-1;$j>=0;$j--) {
echo $charSet[$base[$j]];
}
echo '<br/>';
}
// How many $base elements reached their max?
for($i=0;$i<$baseSize;$i++) {
if($base[$i] == $size-1$counter++;
else break;
}
// Every array element reached max value? Expand array and set values to 0. 
if($counter == $baseSize) {
// Notice <=$baseSize! Initialize 0 values to all existing array elements and ADD 1 more element with that value
for($i=0;$i<=$baseSize;$i++) {
$base[$i] = 0;
}
$baseSize count($base);
}
// Carry one
else {
$base[$counter]++;
for($i=0;$i<$counter;$i++) $base[$i] = 0;
}
$counter=0;
}
?>
Non va bene perché genera le stringhe una ad una prima di stamparle. Il tutto devo riuscire a farlo senza DB e senza file intermedi tipo file xml o di testo.

Ringrazio in anticipo tutti quelli che hanno perso tempo a leggere questo post e spero in una risposta che risolva il mio problema.

Saluti
Registrato
M.A.W. 1968
** LEGGETE IL REGOLAMENTO ! **
Global Moderator
Hero Member
*****

Karma: +224/-19
Scollegato Scollegato

Messaggi: 2988


Discrete And Combinatorial Mathematics


Mostra profilo WWW
« Risposta #1 inserita:: Gennaio 29, 2016, 05:45:00 »

Per ovvi motivi religiosi non posso sporcare il mio Karma avvicinandomi a codice php  Pianto

Comunque, qual è il problema? Si tratta di scegliere un algoritmo per la generazione di subpermutazioni con ripetizioni non ristrette di ampiezza k=3 da un insieme di n=26 simboli. A tale scopo va benissimo anche il classico algoritmo di Rohl riveduto e corretto da Ganapathi e Rama, del quale ho recentemente trattato qui.

Per ogni permutazione generata, invece di procedere banalmente con la stampa, si entra in una seconda funzione che accetta tale permutazione come parametro (sarà il prefisso del codice generato) e genera nel modo più banale, con un doppio loop annidato, i suffissi alfanumerici, stampando così ad ogni iterazione del loop più interno il risultato ottenuto giustapponendo il prefisso e la stringa suffisso, comprensiva del carattere di separazione e con la formattazione desiderata.

Per ogni permutazione saranno generati 26·99=2'574 prefissi, e dal momento che le permutazioni con ripetizioni PR(26, 3) sono pari a 263=17'576, si avrà un totale di 45'240'624 stringhe distinte. Ovviamente la complessità computazionale è a dir poco disastrosa, me non vi sono molte alternative parlando di generazione esaustiva (e comunque i numeri coinvolti sono ancora ampiamente trattabili).
Registrato

I Moderatori invitano tutti gli utenti a prendere visione del REGOLAMENTO e a rispettarlo.

Un blog? Io? Occhiolino
noob.81
Newbie
*

Karma: +0/-0
Scollegato Scollegato

Messaggi: 3


Mostra profilo E-mail
« Risposta #2 inserita:: Gennaio 29, 2016, 06:17:23 »

 Scioccato
Registrato
Pagine: [1]   Vai su
  Stampa  
 
Vai a:  

Copyright © 2017 Edizioni Master SpA. p.iva : 02105820787

Tutti i diritti di proprietà letteraria e artistica riservati. - Privacy



powered by Simple Machines