Newsgroup: it.comp.programmare
Titolo: Quesito solo apparentemente banale!

85-86-87-88-89-90  622ªmilionesima(circa) Colonna
[Avrei dovuto snippare questo pezzo, ma lo tengo a memoria di una grossa
cantonata]
Scusa, perche' 622-milionesima?
La prima colonna puo' assumere 90 valori.
La seconda puo' assumere uno degli 89 rimanenti.
La terza uno degli 88 rimanenti
La quarta pesca su 87
La quinta su 86
La sesta e ultima su 85.
Le possibili estrazioni sono 90!/(90-6)! che e' maggiorante di (90-5)^6,
e visto che log(85) e' circa 1.9, parliamo di 10^11 circa, mentre 622E6,
appunto, e' meno di 10^9.
Cosi' a occhio e croce dovrebbero venire cinquecento MILIARDI di colonne
e non 622 MILIONI.
Dove sbaglio? Di lotto, non so un accidente. Forse i numeri devono avere
sempre un ordine crescente? Questo diminuirebbe di un fattore 6!, e piu'
o meno saremmo nell'ordine di grandezza giusto... evabbe', facciamoci il
conto:
	90*89*88*87*86*85 / 6*5*4*3*2*1 =
	= 90/6 * 88/4 * 85/5 * 87/3 * 86/2 * 89/1 =
	= 15 * 22 * 17 * 29 * 43 * 89 =
	= 622.614.630 ... uh oh :-)
[fine della solenne cantonata]
E in effetti poter mappare i numeri su 622 milioni e' comodo, perche' la
colonna standard di 90^6 sono 39 bits (circa), mentre 622 milioni ci sta
pulito, in 32 bits; con un ovvio risparmio, per tenere un database delle
estrazioni.
Parto subito, dicendo che non so se si possa costruire una funzione come
dici tu. Nel caso dell'immagazzinamento per database pero' si puo' forse
fare qualcosa usando degli offsets variabili. Cosi' molto a occhio, sono
abbastanza sicuro che *potrei* codificare una sequenza crescente, di sei
numeri da 1 a 90, in 32 bits. Il dubbio e' se e' questo che ti serve, mi
sa che mi sono fatto un po' trasportare.
Parliamone ;-)
Leonardo
-- 
".signature": bad command or file name

 ha scritto nel messaggio
news:vek13t0taocmh3jgv...@4ax.com...


del sistema!
long lotcount(int *colonna)
{
    int i;
    long x = 0;
    for (i=0; i < 6; i++)
        x = x*9 + colonna[i] - 1;
    return x-8303;
}
#####
Per esempio, inizio a calcolare da 2-4-7-11-22-30 e voglio andare avanti
fino a 85-86-87-88-89-90:
	lotcount(2-4-7-11-22-30) = 75831
	lotcount(85 86 87 88 89 90) = 5580120
quindi delta sul codominio e' 5504289... Quando sono a 40 41 42 43 44 45
lotcount vale 2590770, 2590770-75831 = 2514939, 2514939/5580120 = 0.4507
e quindi sei al 45.07% del percorso :-)
Questo suggerimento e' Agent-ware: se funziona, sei moralmente impegnato
ad andare su 
www.forteinc.com
 e a installare Free Agent (gratis), invece
di quel cesso di Outlook che ti fa quotare da fetenzìa :-)
Tra l'altro mi sono messo a studiare una funzioncina scema, che comprime
sei estrazioni a un numero a 32 bits. Se ogni giorno fanno un'estrazione
riesco a fare stare dieci anni di estrazioni su venti ruote in 300K. Poi
vedro' come si puo' implementare una ricerca un po' veloce a colpi di OR
e AND :-)
(Bello... potrei farcelo stare sul Palm Pilot, insieme al database con i
codici fiscali degli ottomila uffici IVA d'Italia [1]).
Leonardo
[1] 35Kb


 ha scritto nel messaggio
news:dju33tohe1m7ktjt4...@4ax.com...


 ha scritto nel messaggio
news:3a327...@news.dada.it...


sei estrazioni a un numero a 32 bits. 
come fai?




Sto studiando varie possibilita'.
Per esempio, la somma dei "delta" fra un numero e l'altro ovviamente e'
costante (e vale 84). Quindi se riuscissi a codificare questo delta con
pochi bits quando e' piccolo, e piu' bits quando e' grande... e tenendo
conto ovviamente che anche piccolo/grande e' un'informazione che usa un
certo numero di bits...
(C'era una codifica del genere per gli hard disks, ARLL mi pare...)
Leonardo


> numero di colonne che matematicamente è possibile generare?
Si'. La prima funzione che ti ho dato ha delle inversioni, e piu' valori
si sovrappongono. In pratica, 20 50 60 e 20 49 69 danno lo stesso valore
in uscita (per esempio).
Questo perche'... da autentico fessacchiotto, ho tolto uno zero dove non
avrei dovuto :-)
Attenzione, perche' ora il valore in uscita non e' piu' un longint.
Leonardo


Sto studiando varie possibilita'.
Questo che segue e' un esempio di quello che dicevo. Si tratta di un
grosso numero di estrazioni, generato con il programma C di cui all'
allegato (A) ;-). E da questo viene generato la tabella di frequenza
dei delta:
400416  377219  355565  335794  315879  297520  279107  263516
246980  232807  217049  203549  191116  177758  166207  155638
143728  134842  124837  116573  108268  100085  93547   86115 
79853   73579   67948   62564   57352   52504   48420   44061 
40343   36660   33543   30271   27474   25105   22670   20400 
18525   16379   14893   13165   11869   10355   9233    8171  
7278    6312    5455    4861    4169    3679    3143    2642
2302    1938    1644    1363    1186    955     832     619     
486     429     309     228     177     158     94      100     
72      38      29      18      10      10      6       5   
1       0       0       0
Per codificare un delta, mi ci vogliono sempre 7 bits... in realta',
qualcosina meno, perche' 7 bits codificano 128 stati, ma a me qui ne
bastano 85 (il primo numero possibile e' 1, il secondo al massimo e'
86).
Ora, la cosa bella e' che su sei numeri, al massimo posso avere "UN"
delta uguale a 45; di delta "piccoli" ne posso avere sei, e finire a
una "quota" piu' bassa. Per esempio 1-2-3-4-5-6.
Se potessi quindi codificare usando 5 bits per i delta piccoli, e un
numero maggiore per i delta piu' grandi, sarei un bel pezzo avanti.
Usando i simboli A-Z, a-z, 0-9 e i caratteri di interpunzione, posso
ottenere una traduzione ASCII di una estrazione con i delta (di cio'
se ne occupa la funzione in all. B). E con i dati tradotti ora posso
fare un po' di esperimenti usando la compressione Huffman statica.
Per i VB-isti: 
http://www.astraware.com/program/vbhuffman.html
Un esperimento abbastanza rozzo mi dice che posso comprimere una run
standard in 28 bits, di media. Il problema sono i casi peggiori :-)
+++
All. A - il programma (the program)
#include <stdio.h>
int		v[7],
		d[7];
long	x[90];
void ordina()
{
	int i, j, k, z;
	for (i=0; i < 6; i++)
	{
		for (j=0; j <= 5; j++)
		{
			for (k=j+1; k <= 6; k++)
			{
				if (v[j] > v[k])
				{
					int z;
					z = v[j];
					v[j] = v[k];
					v[k] = z;
				}
			}
		}
	}
}
void estrai()
{
	int i, j, o;
	for (i=1; i <= 6; i++)
	{
		o = 0;
		while(!o)
		{
			o = 1;
			v[i] = (random()%90) + 1;
			for (j=1; j < i; j++)
				if (v[j]==v[i])
					o = 0;
		}
	}
}
void calcola()
{
	int i, dd;
	for (i=1; i <= 6; i++)
	{
		dd = v[i]-v[i-1];
#ifdef DEBUG
		if (dd <= 0 || dd > 85)
		{
			printf("ERRORE, v[%d]=%d, v[%d]=%d\n",
i,v[i],i-1,v[i-1]);
			exit();
		}
#endif
		x[dd]++;
		d[i]=dd;
	}
}
#define LIMIT	1000000
#define K		(LIMIT/16)
int main()
{
	int j;
	long i;
	v[0]=0;
	d[0]=0;
	for (i=0; i < 85; i++)
		x[i] = 0;
	for (i=0; i < LIMIT; i++)
	{
		estrai();
		ordina();
		calcola();
		if (((i%K) == 0) || (i == (LIMIT-1)))
		{
			for (j=1; j < 90; j++)
			{
				printf ("%ld	", x[j]);
				if (j%7 == 0)
					printf("\n");
			}
			printf("\n---------------------------\n");
		}
	}
	return 0;
}
All. B La funzione (the function)
void traduci(void)
{
    static const char traduzione[]= "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                                    "abcdefghijklmnopqrstuvwxyz"
                                    "0123456789|!£$%&/()=?^"
                                    "אטילעש{[]}+-*.,:;";
    int i;
    for (i=1; i <= 6; i++)
        printf("%c", traduzione[d[i]]);
    printf("\n");


 [...]
Scusa, ma il problema che ti sei posto č semplicemente impossibile!
NON puň proprio esistere un algoritmo che "comprima" una _qualsiasi_
estrazione del superenalotto (6 numeri) in 32-bit, per quanto uno possa
sforzarsi o per quanto geniale possa essere l'algoritmo.
Infatti, basta pensare che, come dicevi, le estrazioni possibili sono 622
milioni e rotte, mentre con 32-bit hai un massimo di combinazioni di...
Vabbč lo sappiamo tutti no? :-)))
Qualsiasi sia l'algoritmo, a qualcuno dei numeri a 32-bit
corrisponderebbero, necessariamente, piů estrazioni e quindi non potresti
ritornare indietro (cioč risalire all'estrazione di partenza dal numero a
32-bit)
Altro che funzioncina scema! Sarebbe una funzioncina miracolosa!! :-)
Ciao

Vabbč lo sappiamo tutti no? :-)))
Quattro miliardi e rězzati. Che e' appunto un bel po' piu' di 622
milioni.
Dai, Stefano. Saro' pazzo, ma non COSI' scemo :-)


 wrote in message
7n4i4tkee156qvu5f...@4ax.com...

Ehmm... Hai ragione, piccolo lapsus: anche se ho scritto "32-bit", stavo
pensando alle 65536 combinazioni che hai con 16-bit.
E il bello č che ho pure scritto "lo sappiamo tutti" :-)))
Vabbč, per riprendermi dalla cantonata ti ho trovato la soluzione al
problema,
cioč una funzione (io l'ho fatta in Visual Basic), che prende in entrata un
array con i 6 numeri da 1 a 90, in ordine crescente e senza ripetizioni, e
ti restituisce
il numero progressivo di quella particolare colonna in formato "intero a 32
bit"
(che poi č anche la soluzione al secondo problema di comprimere sei numeri
in 32-bit).
Per "numero progressivo" faccio riferimento all'ordinamento abbastanza
intuitivo delle possibili colonne:
Esempio:
Numero progressivo                Colonna
1                                            1    2    3    4    5    6
2                                            1    2    3    4    5    7
....
85                                          1    2    3    4    5    90
86                                          1    2    3    4    6    7
Etc.
L'array con i 6 numeri deve essere preventivamente ordinato per numeri
crescenti e controllato (niente ripetizioni, solo numeri da 1 a 90)
affinché la funzione funzioni.
"estratti" č un array (1 to 6) di interi.
--------Soluzione-----
Function numero_colonna(estratti%()) As Long
Dim i%, j%, preced%, numero As Long
numero = 0
For i = 1 To 5
 If i = 1 Then preced = 0 Else preced = estratti(i - 1)
 If estratti(i) > (preced + 1) Then
  For j = (preced + 1) To (estratti(i) - 1)
   numero = numero + coeff_binom(90 - j, 6 - i)
  Next
 End If
Next
numero = numero + estratti(6) - estratti(5)
numero_colonna = numero
End Function
--------------------------
Dentro compare la funzione "coeff_binom(n,k)" che non č altro che il
coefficiente binomiale di n,k e vale:
coeff_binom(n,k) = n! / [ k! * (n-k)!]
Occhio, perň, che con numeri cosě grandi capita facilmente di andare in
overflow o di avere errori dovuti alla precisione.
Per non aver problemi io l'ho implementata cosě:
------------------------------
Function coeff_binom(n%, k%) As Long
 Dim app As Double, ii%
app = 1
If k < n Then
 For ii = (n - k + 1) To n
  app = app * ii
 Next
 app = app / fatt(k)                     '    "fatt(k)" vale k!
End If
coeff_binom = Int(app)
End Function
------------------------------
E, come per magia, funziona! (Vabbč č matematica)
In particolare, all'ultima colonna   (85    86    87    88   89     90)
la funzione assegna il numero 622614630    che č proprio il numero delle
combinazioni possibili
Fammi sapere, ciao!
Stefano

problema,
Caspita, i coefficienti binomiali! Questa si' e' una ganzata 8-(
(la faccina e' triste perche' avrei dovuto pensarci io. Ma credo
sia passato troppo tempo da quando l'ho studiato e probabilmente
non li ho mai saputi usare troppo bene).
Chapeau.
Leonardo ammirato
