Newsgroup: it.hobby.lotto
Titolo: Ridotti!!!

Qualcuno si è mai occupato di algoritmi di riduzione? Sono molto
interessato alla faccenda, visto che dispongo di una notevole potenza
di calcolo (k6 200) che vorrei mettere all'opera su qualcosa di utile.
Accetto qualsiasi consiglio.
Ciao, Piero.

di calcolo (k6 200) che vorrei mettere all'opera su qualcosa di utile.
il mio 486 ci ha impiegato 35 ore, sarei curioso di sapere come va il k6
Ciao
Marco
---------------------------------------
"Il senno di poi è una scienza esatta."

Allora: innanzitutto io ho iniziato con il Totocalcio i miei studi sui
ridotti, e pertanto parlerò di lui. Comunque credo che con poche
modifiche si possa estendere il discorso ad altri giochi.
Comincerei quindi dal semplice n-1, perchè credo (ad occhio) che gli
altri ridotti siano più complessi, oltre ad essere inutili nel
Totocalcio... ;)
Inoltre il problema secondo me potrà dirsi risolto solo quando sarà
possibile ridurre un generico insieme di colonne. Cominciamo...
Allora, io parto da un insieme di colonne che chiamo Z; diciamo che
sono n. Prendo la prima colonna; questa 'copre' (oltre a se stessa)
tutte quelle che differiscono da lei per un solo segno. Non sappiamo
quante di queste 26 colonne appartegano a Z. Indico con M1 quante
colonne copro con la prima colonna; questo numero va da 1 a 27 (se
stessa senz'altro la copre), a seconda di quante colonne simili ci
sono tra le n-1 rimaste; il pedice 1 (qui pedice non è...) indica che
ci si riferisce alla prima colonna. Suppongo inoltre di segnarmi gli
M1 numeri delle colonne coperte. Ho quindi un insieme di M1 numeri,
che chiamo A1.
Ora io prendo la prossima colonna e ripeto la stessa operazione, e
così via per ogni colonna dell'insieme. Ottengo quindi n insiemi di
colonne (da A1 ad An), ognuno con un diverso numero di colonne al suo
interno.
Ora per ogni colonna faccio questa ricerca: in quali tra gli n insiemi
A1-An questa colonna compare? Se scopro che la colonna in esame viene
coperta solo da un certo insieme, ho scoperto il primo punto fisso
della mia vita; quell'insieme andrà giocato senz'altro. E poichè ad
ogni insieme corrisponde la colonna che lo ha generato, posso dire più
correttamente: la colonna che ha generato quell'insieme andrà giocata.
Osservo inoltre che la colonna che ha generato l'unico insieme in
grado di coprire la colonna in esame è esattamente la colonna in
esame. (Complicato da dire ma ovvio)
Stessa cosa in altre parole: se una colonna non viene coperta da
nessun'altra dell'insieme di partenza, la devo giocare per forza nel
mio ridotto! E per non venire coperta da nessun'altra colonna, è
sufficiente che essa differisca per almeno due segni da tutte le
altre.
Primo passo dell'algoritmo: cercare le eventuali colonne che
differiscono per almeno due segni da tutte le altre; queste faranno
senz'altro parte del ridotto.
Rimane quindi un insieme di colonne con una antipatica proprietà:
tutte le colonne differiscono per un solo segno da qualcun'altra
dell'insieme. Questo insieme lo chiamerò Y.
Bhé. per oggi basta senò non mi legge più nessuno. Vorrei solo sapere
se l'esposizione è chiara, se avete commenti o suggerimenti. Ora
bisogna ridurre Y, e qui vi anticipo che non ho una soluzione univoca,
e quindi cerco il vostro aiuto.
Secondo me, però, l'impostazione degli n insiemi A1-An, è utilissima
(anche se ora come ora non saprei dirvi perchè, ma lo sento...). Per
il primo passo chiaramente non serve a nulla, ma credo sia essenziale
per i successivi.
Ciao, Piero.

 Ciao, Piero.
CIAO
se sei interessato alLE RIDUZIONI  superenalotto
prova a scaricare la versione 1.00
di SUPERENALOTTOMANIA 1.00
qui:
http://151.99.197.24:80/VOLFTP/Scheda.exe?it/enalotto.exe
e poi visita il mio sito
http://users.iol.it/chiales
bye

Ma per ridurre un sistema, ad esempio di totocalcio, non bisogna partire da una
colonna arbitraria, scelta da me a caso?? (Nel totocalcio non sarebbe poi a
caso...)
Mi spiego meglio: se tu fai tutte le riduzioni, alla fine ottieni N colonne che
ti coprono tutte le possibilità. Queste dipendono in parte tutte dalla prima,
perché se ci sono 2 o più "differenze" diventano una "nuova colonna" altrimenti
no.
In poche parole, la prima colonna è quella che condiziona di più, mentre
l'ultima è quella che "condiziona meno", usata praticamente solo per coprire
qualche (poche) colonna che mancava, mentre la prima sicuramente ne copre 26.
E' giusto?? o ho detto una cavolata??
Allora bisognerebbe trovare le colonne in modo che tutte coprano 26 colonne (o
un po' meno), insomma ricostruire l'insieme di tutte le possibilità P con tanti
sottoinsiemi Q1, Q2... Qn che abbiano intersezione vuota, e che diano come
unione P...
Sembra molto complicato in generale, ma probabilmente in un caso specifico le
cose si semplificano...
Inoltre, non è possibile costruire un algoritmo "diviso" in parti, cioè, per
esempio, che esegua una parte dei calcoli sul mio PC, una su quello di un altro
ecc. ed alla fine si uniscano i risultati... mi pare che i nuovi processori
facciano qualcosa di simile per velocizzare le operazioni...
Se sì mi offro per impiegare il mio P100 per qualsiasi calcolo.
Aspetto (con ansia) vostre risposte...
Emanuele Cesena
d.a.m...@iol.it

Inoltre, non è possibile costruire un algoritmo "diviso" in parti
forse sì e potrebbe essere una strada interessante per ottenere in tempi umani
delle matrici da primato, ma generalmente progettare algoritmi paralleli non è
cosa semplice.
Hai qualche idea?
Ciao


Emanuele Cesena
Ciao, Piero.

Rispondo qui, ma vale in generale...
Io ho parlato di algoritmi di riduzione, ma sinceramente non ne ho mai visto
uno... Che ne dite di iniziare con uno a caso, stupido fin che volete, poi
tentiamo di renderlo più efficace...
Purtroppo però adesso l'unica cosa che mi viene in mente è di passare una ad una
le possibili colonne ed eliminarla se è già coperta, ma è talmente lungo che mi
viene schifo solo a proporlo...
Se non sbaglio Marco ne ha già uno per il SuperEnalotto... si può provare a
partire con quello (se a voi va bene...)
Alla prossima...
Emanuele Cesena
d.a.m...@iol.it

partire con quello (se a voi va bene...)
non ho capito se vuoi lo pseudo-codice o proprio il codice C++
Ciao
Marco


non ho capito se vuoi lo pseudo-codice o proprio il codice C++
Preferirei lo pseudo codice, perché ho paura di non capirlo tutto in C++
Ciao
Emanuele Cesena
d.a.m...@iol.it

Preferirei lo pseudo codice, perché ho paura di non capirlo tutto in C++
allora non sei stato attento, già l'ho scritto :-))
prendi 2 insiemi (set, array, liste, quello che vuoi)
nel primo metti le colonne di partenza (ad esempio l'integrale, nel qual caso
puoi generarlo on the fly, anzichè memorizzarlo) nel secondo metterai le colonne
che formeranno il ridotto
1- comincia con la prima colonna dell'integrale e la butti nel ridotto
2- prendi la colonna successiva dell'integrale e la confronti con quelle del
ridotto (al momento una sola): se è già coperta la vincita butti la colonna
corrente, altrimenti la aggiungi. Ad es: 
1 2 3 4 5 6 7 8 sia la prima colonna
1 2 3 4 5 6 7 9 sia la seconda, che realizza il 7 sette sulla prima, quindi la
buttiamo, mentre terremmo la 1 2 3 4 5 6 9 10 che farebbe solo 6
3- ripeti il passo 2
* Non è necessario confrontare la colonna con tutte quelle che hai già messo da
parte, ma puoi fermerti appena vedi che la colonna è già coperta e puoi buttarla
* conviene fare il cofronto a partire dalle ultime colonne accettate, anzichè
dalle prime, perchè queste sono mediamente le più simili e quindi puoi decidere
già dai primi confronti che la colonna può essere buttata. Infatti la maggior
parte delle colonne vengono buttate e solo una piccola parte resta nel ridotto,
soprattutto quanto più la categoria è bassa
