Newsgroup: it.comp.www.php
Titolo: Soluzione da file

Buonasera a tutti,
Sto eseguendo uno script molto complesso a livello di calcolo.
Ho un numero Dn che cresce in maniera esponenziale a secondo di n.
Gia per n = 11 abbiamo Dn=14684570.
Per spiegarmi meglio Dn è il numero di permutazioni senza ripetizioni
di una serie di numeri di lunghezza n.
Per calcolarmi ogni permutazione di 11 ho bisogno di tutte le
permutazioni di 10. Quindi devo memorizzare queste permutazioni. Ad
esempio se l'utente vuole tutte le permutazioni senza ripetizioni di
8, devo calcolare prima quelle di 7, per 7 devo calcolare quelle di
6...insomma una ricorsione.
Essendo i dati veramente tanti, non è possibile fare tutto tramite uno
script memorizzando in matrici o array queste permutazioni. (matrici
da 14684570 righe e piu)
Quindi pensavo di utilizzare dei file di testo. Quindi, ad esempio, se
vogliamo trovare tutte le permutazioni s.p.f di 6.
Trovo le permutazioni di ordine 2(che è una), memorizzo. Trovo le
permutazioni di ordine 3 leggendo quelle di ordine 2, memorizzo. Trovo
quelle da 4 leggendo quelle da 3..ecc. fino ad arrivare a 6. E alla
fine avrò dei file, dove ognuno conterrà la lista di tutte le
permutazioni del proprio ordine. Insomma moltissime letture e
scritture su file!!!
- Mi conviene una soluzione del genere?
- I file si possono tenere aperti? o ad esempio leggo una delle
permutazioni di un file e poi devo chiuderlo?
- Se si possono tenere aperti, c'è un limite di tempo?
Spero di essere stato chiaro,
Grazie Mille,
Marco Angelini

 
Non entro nel merito della questione, ma invece di utilizzare i file, 
usa un database: gestione dei dati semplificata, possibilità di far 
eseguire anche dei calcoli al dmbs etc....
	Francesco

 chiuderlo? - Se si possono tenere aperti, c'è un limite di tempo?
Ti conviene usare un database. Fai una tabella piu` o meno cosi`:
create table perm (
  ordine int,
  permutazione int,
  index (radice)
);
Per trovare tutte le permutazioni di 6 (per dire) ti basta:
select * from perm where ordine=6;
Bye.

 Bye.
Ciao,
Grazie per le risposte.
Volevo evitare di usare un database, ma effettivamente è la miglior
soluzione.
Saluti,
Marco Angelini

 soluzione.
Se non vuoi tutto il motore dietro che gira, usa SQLite, che usa un solo 
file.
Bye.


Ho già installato il motore che gira dietro, userò XAMPP.
A questo punto vi chiedo una ultima cosa(spero).
Voglio una tabella per ogni permutazione di ordine n. Quindi se voglio
creare il listato delle permutazioni di lunghezza 11, devo prima
creare tutto il listato delle precedenti permutazioni 10,9,8,7,6, ecc.
Quindi faccio un ciclo che controlla se esistano tali tabelle e se non
esistono le crea con un nome che sarà del tipo ordineN dove N è il
numero che indica l'ordine.
Si può fare una cosa del tipo:
CREATE TABLE "ordineN" (ecc.
Dove ordineN è una variabile, se si mi direste la sinstassi?
Mi conviene usare un database che ha una tabella per ogni permutazione
di ordine n con campi: id , permutazione, ordine..???
Per vedere se c'è la lista delle permutazioni di ordine n si guarda se
esiste la tabella che si chiama ordine"n".
Ricordo che il numero di permutazioni Dn di ordine n cresce in maniera
esponenziale già con n=11 abbiamo la tabella ordine11 con 14.684.570
righe
Spero di essermi spiegato correttamente
Saluti,
Marco.

 ordine11 con 14.684.570 righe
A maggior ragione un DB, con le giuste query (asincrone) e indici (nei 
campi giusti) ti permette di evitare di caricare in RAM tutte le 
permutazioni possibili. Sara` magari piu` lento che lavorare in RAM, ma ti 
permette di arrivare tranquillamente (spazio disco permettendo) a 
permutazioni di ordine 20 o 30.
Pero` se fossi in te valuterei la possibilita` di usare linguaggi diversi 
da PHP, se i calcoli sono (come sembra) molto pesanti. Puoi usare PHP come 
interfaccia, e dietro scrivere la funzione di calcolo in C o in Fortran, o 
magari in python usando una delle varie librerie per calcolo scientifico 
(compilate, quindi quasi con le stesse prestazioni del C, sempre usando le 
funzioni giuste).
Bye.


Grazie,
penso che se riesco ad arrivare ad un ordine pari a 20 gia è
abbastanza.
Provo a farti un ragionamento partendo da un esempio:
Abbiamo n=5;
Quindi prendo tutte le permutazioni di lunghezza 4 e le processo una
per una. Ognuna mi darà 4 permutazioni da 5. Quindi se devo calcolare
n perm, prendo le permutazioni di n-1 e avro (numero permutazioni di
n-1)(n-1) = numero permutazioni di n (che poi non sono tutte)....
Quello che ti chiedo è:
E meglio fare una unica query che me le prende tutte le permutazioni
di lunghezza 4 e poi le processo o è meglio prendere una permutazione
e processare, per poi prenderne un'altra e poi processarla, ecc.?
Avremo cosi milioni(se non di piu) di query per n molto grande. Ma
cosi facendo, dico io, il programma sarà molto piu lento ma il consumo
di memoria è minore e cosi facendo possiamo arrivare a n piu
grandi...o sto dicendo la stessa cosa che mi hai detto prima in parole
diverse?
L'importante di quello che sto facendo non è la velocità, ma la
potenza...senza esagerare. :) se arrivo a 25 è eccellente!!!!
Cmq grazie ancora,
Marco

 potenza...senza esagerare. :) se arrivo a 25 è eccellente!!!!
Mi intrometto solo ora....per chiedere una cosa....ma la permutazione,
la vuoi fare di cosa??
Tu hai detto che vuoi trovare il numero di permutazioni senza
ripetizioni di una serie di numeri di lunghezza n.
Ma i numeri...son sempre gli stessi? Perché altrimenti a che ti serve
il database? E inoltre..perché solo di numeri, e non genericamente di
"simboli", o "parole"?
Esempio:
n=3   15 20 10
permutazioni possibili:
15 20 10
15 10 20
20 15 10
20 10 15
10 15 20
10 20 15
Ma ciò che mi chiedo io è, a che ti serve il database in questo caso?
Per memorizzarci cosa? E se cambio i numeri? E se uso lettere?
O mi son perso qualcosa? :)
-- 
rob4you

di una serie di numeri di lunghezza n.
E a cosa ti servono tutte queste permutazioni? Cioe', diciamo che tu abbia
la permutazione { x1..x11 }, che ci fai poi?
Leonardo
-- 
While ordinarily valid that being widespread does not make a statement
true, I feel that the diffusion of anti-evolutionary beliefs does pose
a strong argument for Darwin having been, indeed, sorely mistaken.

 O mi son perso qualcosa? :)
Ti spiego:
La serie di numeri è sempre composta da  numeri da 1 a n. Quindi se
n=11 le permutazioni vanno da 1 a 11.
Una permutazione senza ripetizioni è una permutazione tale che f(x) !=
x per ogni x
Quindi con n=4 abbiamo la serie che è 1234 e le permutazioni senza
punti fissi sono:
4321
4312
4123
3412
3421
3142
2143
2341
2413
2341
Se non ho sbagliato sono queste. Comunque se il numero di queste
permutazioni lo chiamiamo Dn(D4 nel caso di 4). Abbiamo che:
Dn = (n-1)(Dn-1 + Dn-2) Quindi le Dn dipendono dalle due Dn
precedenti. Quindi se devo trovare le D8, devo calcolare tutte le Dn
precedenti, perchè mi serve D7 e D6, ma per trovare queste due mi
servono quelle precendenti....Insomma si parte dalla piu piccola fino
ad arrivare al quella che mi serve.
Si potrebbe fare un algoritmo che sfrutta una ricorsione ma:
D1 = 0
D2 = 1
D3 = 2
D4 = 9
D5 = 44
D6 = 265
D7 = 1854
D8 = 14833
D9 =133496
D10 =1334961
D11 =14684570
D12 =176214841
Quindi immagina per D12 quanta memoria mi occorre.
A me piacerebbe arrivare intorno a D20 o addirittura a D25. Dn
talmente grandi che non so neanche leggere... :)
Ed è per questo che mi appoggio ai database. In tal modo trovato un Dn
lo metto nel db, e per trovare Dn+1 non c'è bisogno che alloco tutto
Dn in memoria perchè è gia dentro il db. Poi prendo un elemento di n
alla volta per calcolare un elemento di n+1 e cosi via....miglioni di
query insomma, ma cosi facendo credo si possa arrivare a Dn piu
grandi, purtroppo la velocità ne risente di molto, ma poco importa!!
Non so quanto sono stato chiaro. Spero di si.
Ciao ciao
Marco

 la permutazione { x1..x11 }, che ci fai poi?
Trovate tutte le permutazioni senza ripetizioni di lunghezza 11 le
metto nel db. Poi l'utente tramite query che ancora non ho fatto ne
sceglie una. Di questa che ha scelto viene fatta la scomposizione in
cicli e trovato il numero di ripetizioni e altre cose. Insomma una
cosa molto didattica. Diciamo che questa è la prefazione alla mia tesi
di laurea. Le permutazioni senza punti fissi hanno proprietà
interessanti (cosi dice il prof)...:).....e quindi la tesi sarà
centrata su fare applicazioni per il web che studino queste
proprietà....Ma ho appena iniziato quindi piu di cosi non so che
dirvi!!!
Ciao ciao

precedenti, perchè mi serve D7 e D6
No, non necessariamente. Puoi generarle anche in modo non ricorsivo, ma
anche ricorsivamente mica ti serve cosi' tanta memoria: ti basta che tu
salvi lo "stato" del permutatore e sei a posto.
Mi pare una volta di aver scritto qualche cosa che convertiva un numero
nella corrispondente permutazione, ma non ritrovo il post su Google. In
quel caso avresti dovuto fare
	for ($i = $D10; $i < $D11; $i++)
		print linear2permute(11, $i) . "\n";
per avere la lista.


sceglie una.
Penso che qui si possa non usare affatto il DB e usare invece astutamente
l'interfaccia utente.
Per esempio, potresti fargli scegliere la permutazione con tante chiamate
a quella pagina quanti sono i simboli.
All'inizio, metti in sessione {A=5,B=2,C=3,D=1} e proponi all'utente, con
una drop box a discesa, array_keys($v) - cioe' A, B, C o D - come "primo"
simbolo.
L'utente sceglie B, quindi la pagina viene chiamata con s="B" e il solito
v. Esplori tutto "s" e ogni volta che trovi il simbolo X decrementi v[X],
e if (0 == $v[$x]) unset($v[$x]); ... in questo modo, automagicamente hai
che array_keys ti da' la lista dei simboli disponibili.
A ogni passaggio puoi anche fornire il numero di permutazioni disponibili
con i simboli rimanenti.
In questo modo non usi il DB, ogni passaggio e' pressoche' istantaneo, ed
hai alla fine il tuo $s con la permutazione scelta. Tutti sono contenti e
puoi proseguire :-)
Leonardo imbroglione



Non ti seguo, cosa intendi per stato del permutatore?



Ciao,
Come dici tu alla fine di tutto non ho tutte le possibili permutazioni
di n...o mi sbaglio?
E poi devo applicare l'algoritmo che descrivevo all'inizio non posso
fare di testa mia.
L'agoritmo che devo applicare è quello che dice:
Dn = (n-1)(D(n-1) + D(n-2))...Se abbiamo n=10 vuol dire che possiamo
ricavare 9 permutazioni di ordine 10 da ogni permutazioni di ordine 9
e 9 permutazioni di odrine 10 da ogni permutazione di ordine 8.
Quindi devo usare per forza le permutazioni precedenti.
Alla fine di tutto abbiamo tutto il listato delle permutazioni da 2 a
n. Penso che i db siano la scelta migliore.
ciao ciao
Marco

Penso che i db siano la scelta migliore.
Forse la piu' lineare. Ma del resto anche per sommare i numeri da 1 a N
il modo piu' lineare e' la sommatoria, mica il metodo di Gauss :-)
Tutto si gioca sul cosa devi fare, DOPO, con quella permutazione. E non
e' nemmeno detto che sia un vincolo.
Leonardo




Scusami ma non ti seguo.
Io alla fine voglio tutte le permutazioni di n e non solo quella che
sceglie l'utente...
A me sembra che la tua soluzione arrivi a trovare una sola
permutazione di n...
O forse mi sbaglio??
Marco

O forse mi sbaglio??
Esatto. Supponi che l'uso che si vuole fare di questa permutazione sia,
che so, formare un numero esadecimale ed estrarne la radice quadrata.
Non hai bisogno di generarti TUTTE le permutazioni per raggiungere quel
che e', di fatto, l'obiettivo -- fornire all'utente una radice.
Basta che tu sia in grado di generare ogni volta quell'una permutazione
che il cliente ti richiede. Come fa a sapere che tu non le hai davvero,
dentro?
Il discorso cambia se il cliente potesse chiedere "Me ne da' mille?". A
quel punto, il tempo di generarne mille e' troppo lungo, e il trucco si
vedrebbe (forse).
Ma finche' l'utente deve selezionare UNA permutazione per volta...


 Ma finche' l'utente deve selezionare UNA permutazione per volta...
La questione dell'utente che ne sceglie una viene dopo, io prima
voglio tutte le permutazioni di ordine n. E se cmq uno volesse tutte
le permutazioni di ordine 6 che inizino per 321 e poi sceglierne una
di queste....
La questione iniziale era in che modo potevo lavorare con i dati
generati dal mio algoritmo e non un algoritmo differente!!!
Cmq sia adesso ho capito perfettamente la tua idea e non è affatto
male. Come dici tu infatti non avrei assolutamente problemi di
grandezza. Potrei arrivare a calcolare permutazioni di ordine
incredibilmente grande. Grazie per i consigli.
Ciao ciao
Marco.

 2341
Non so se ho capito bene, ma in tal caso tu andresti a salvare nel
database queste dieci righe che hai calcolato sopra.
Ma quello che mi chiedo io è: se la serie non è 1234 ma 1423, oppure
ABCD, oppure 7890, oppure genericamente xyzk, come la gestisco la cosa?
Cioè, a che ti serve il databse in questo caso?
Non riesco ancora a capire il punto centrale. :)
-- 
rob4you


La serie va sempre da 1 a n.
Il database mi serve diciamo come appoggio, se usassi solo la memoria
non riuscirei ad arrivare ad n elevato.
Ciao ciao