[?] Creare tutte le combinazioni possibili.
Esteban
Un mio amico mi ha chiesto di trovare tutte le combinazioni possibili di un
gruppo di numeri.
Ho pensato subito di usare dei clicli For...Next per trovare le varie
combinazioni, ma poi ho capito che non è la via migliore, anche perché non
so da quanti numeri è formato il gruppo.
Esempio:
-dato il gruppo di numeri: 2, 5, 8, 9
-ho pensato di creare un'array di 4 elementi:
Dim lngArray(0 To 3) As Long
lngArray(0) = 2
lngArray(1) = 5
lngArray(2) = 8
lngArray(3) = 9
- a questo punto, faccio 4 clicli For...Next:
For a=0 To 3
For b=0 To 3
For c=0 To 3
For d=0 To 3
Debug.Print "Combinazione:", lngArray(a), _
lngArray(b), lngArray(c), lngArray(d)
Next
Next
Next
Next
1) E' chiaro che se gli elementi sono (p.e.) 40 mi perdo nei cicli
For...Next;
2) Se poi gli elementi sono in quantità variabile, una soluzione di questo
tipo è impensabile.
Mi sto scervellando per trovare una soluzione, ma non ne vengo a capo.
Qualcuno ha un'idea di come possa fare?
Grazie!
Esteban
Zanna
> Ciao a tutti!
>
> Un mio amico mi ha chiesto di trovare tutte le combinazioni possibili di un
> gruppo di numeri.
> Ho pensato subito di usare dei clicli For...Next per trovare le varie
> combinazioni, ma poi ho capito che non è la via migliore, anche perché non
> so da quanti numeri è formato il gruppo.
Cerca sul Sito Comune (quando tornerà operativo :P ) "Combinazioni"
Ciao
Davide D'Amico
"Esteban" <esteban_NONSP...@email.it> ha scritto nel messaggio
news:bn0fup$er5$1...@grillo.cs.interbusiness.it...
> Ciao a tutti!
>
> Un mio amico mi ha chiesto di trovare tutte le combinazioni possibili di
un
> gruppo di numeri.
> Ho pensato subito di usare dei clicli For...Next per trovare le varie
> combinazioni, ma poi ho capito che non è la via migliore, anche perché non
> so da quanti numeri è formato il gruppo.
Ma devi essere più preciso:
E' importante l'ordine degli elementi? (in questo caso abbiamo a che fare
con le disposizioni, altrimenti si parla di combinazioni)
Se parliamo di disposizioni... quante volte un singolo numero può comparire?
Dobbiamo distinguere tra combinazioni semplici e con ripetizioni.
Devono essere presenti sempre tutti i numeri nelle combinazioni che vuoi
trovare oppure no?
Il caso più semplice è quello in cui vuoi sapere in quanti modi puoi
raggruppare n elementi presi n alla volta, in questo caso hai una semplice
permutazione e ti basta calcolare il fattoriale. n! = n* (n-1)*
(n-2)........2*1
Ciao.
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.528 / Virus Database: 324 - Release Date: 16/10/2003
Nadir
ti interessano e poi con una semplice queri ottieni tutte le combinazioni
(Conta l'ordine ma puoi aggiungere dei filtri)
ES:
SELECT Tabella1.valore, Tabella1_1.valore, Tabella1_2.valore
FROM Tabella1, Tabella1 AS Tabella1_1, Tabella1 AS Tabella1_2;
"Esteban" <esteban_NONSP...@email.it> ha scritto nel messaggio
news:bn0fup$er5$1...@grillo.cs.interbusiness.it...
Esteban
news:bn0ne8$cm0$1...@newsreader.mailgate.org...
>
> "Esteban" <esteban_NONSP...@email.it> ha scritto nel messaggio
> news:bn0fup$er5$1...@grillo.cs.interbusiness.it...
> un
> > gruppo di numeri.
> > Ho pensato subito di usare dei clicli For...Next per trovare le varie
non
> > so da quanti numeri č formato il gruppo.
> Questa č materia di calcolo combinatorio, basta applicare la formula
giusta.
> Ma devi essere piů preciso:
> E' importante l'ordine degli elementi? (in questo caso abbiamo a che fare
> con le disposizioni, altrimenti si parla di combinazioni)
> Se parliamo di disposizioni... quante volte un singolo numero puň
comparire?
> Dobbiamo distinguere tra combinazioni semplici e con ripetizioni.
> Devono essere presenti sempre tutti i numeri nelle combinazioni che vuoi
> trovare oppure no?
> Il caso piů semplice č quello in cui vuoi sapere in quanti modi puoi
> raggruppare n elementi presi n alla volta, in questo caso hai una semplice
> permutazione e ti basta calcolare il fattoriale. n! = n* (n-1)*
> (n-2)........2*1
Ok, espongo per esteso il problema:
il mio amico ha un'azienda che produce prefabbricati in calcestruzzo.
Ha un banco con cui preparare dei parapetti.
Deve creare un certo numero di parapetti di larghezza differenti.
Il banco ha diversi divisori con cui creare dei parapetti di larghezza
differente.
Il problema č: se il banco č lungo 5 metri, e deve preparare 20 parapetti di
varie dimensioni, come puň combinare i vari divisori per ottimizzare il
lavoro? Cioč, come combinare le varie larghezze per poter ottenere i 20
parapetti con il minor numero di gettate di cemento?
Esempio banale:
il banco č lungo 5 metri, deve preparare 2 parapetti da 3 metri e 2 da 2
metri, se facesse in una sola gettata un pezzo da 2 metri insieme ad un
pezzo da 3 metri, con sole 2 gettate avrebbe prodotto tutti e 4 i pezzi.
Inoltre, piů che aver bisogno di sapere quante combinazioni posso ottenere,
vorrei una mano a capire come devo scrivere il codice per poter ottenere
tali combinazioni.
Grazie per l'interessamento.
Esteban
CSSoft
(snip)
è forse l'algoritmo dello zaino?
--
Salutoni
Sergio
per rispondere... togli il group dall'indirizzo
Zanna
> [Esteban] scrisse:
> (snip)
>
> è forse l'algoritmo dello zaino?
In effetti forse farebbe meglio a cercare (sempre sul Sito Comune) "Best
Fit Ordered"
Ciao
Esteban
news:bn0qjc$s3evp$1...@ID-184808.news.uni-berlin.de...
> CSSoft wrote:
>
> > [Esteban] scrisse:
> > (snip)
> >
> Fit Ordered"
(Quasi) perfetto! Questa č una soluzione sicuramente valida, anche se non č
ottimale.
Infatti, se per esempio ho un banco di 500 cm e i seguenti pezzi:
- 2 pezzi da 200 cm
- 1 pezzo da 80 cm
- 2 pezzi da 50 cm
- ecc...
la routine utilizzata nel programma "Best Fit Ordered" dispone cosě i pezzi
nel primo banco:
2 pezzi da 200 cm e 1 pezzo da 80 cm (totale 480 cm), avanzando 20 cm di
spazio; mentre sarebbe stato piů ottimizzato se avesse messo 2 pezzi da 200
cm e 2 pezzi da 50 cm , senza avanzare spazio.
E' per quello che secondo me dovrei creare una procedura che calcoli tutte
le possibili combinazioni scartando poi le meno ottimizzate.
Comunque grazie Zanna, č da un po' che non bazzico piů in questo ng ma vedo
che sei sempre molto disponibile.
Ciao!
Esteban
Zanna
> "Zanna" <znt....@virgilio.it> ha scritto nel messaggio
> (Quasi) perfetto! Questa č una soluzione sicuramente valida, anche se non č
> ottimale.
> Infatti, se per esempio ho un banco di 500 cm e i seguenti pezzi:
> - 2 pezzi da 200 cm
> - 1 pezzo da 80 cm
> - 2 pezzi da 50 cm
> - ecc...
> la routine utilizzata nel programma "Best Fit Ordered" dispone cosě i pezzi
> nel primo banco:
> 2 pezzi da 200 cm e 1 pezzo da 80 cm (totale 480 cm), avanzando 20 cm di
> spazio; mentre sarebbe stato piů ottimizzato se avesse messo 2 pezzi da 200
> cm e 2 pezzi da 50 cm , senza avanzare spazio.
Il problema che sottoponi non ha un algoritmo ottimale, o almeno non
l'ha considerandolo a stadi infiniti come vorresti tu.
Secondo la tua logica in effeti andrebbe considerata ogni combinazione
possibile, ma questo non č proponibile se anzichč 5 elementi come nel
tuo esempio tu ne avessi n, con n alto a piacere.
Questo perchč i tempi e le risorse impiegate sarebbero improponibili,
inoltre le soluzioni trovate potrebbero essere piů di una.
Algoritmi come il Best Fit Ordered si *avvicinano* al risultato ottimale
(e qualche volta ti va anche bene e lo raggiunge) in modo veloce.
Come puoi notare lui tenta di infilare prima i blocchi piů grossi in
modo che in teoria si riduce lo spreco finale, ma non č affatto detto
che la soluzione proposta sia effettivamente quella ottimale.
Comunque come dicevo nell'altro post, se vuoi provare tutte le
combinazioni cerca appunto "Combinazioni" sul Sito Comune.
Facci sapere se ne tiri fuori qualcosa di interessante.
Ciao