Newsgroup: it.comp.lang.visual-basic
Titolo: [?] Creare tutte le combinazioni possibili.

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.
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

 so da quanti numeri è formato il gruppo.
Cerca sul Sito Comune (quando tornerà operativo :P ) "Combinazioni"
Ciao

 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
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

 ha scritto nel messaggio
news:bn0fup$er5$1...@grillo.cs.interbusiness.it...


 (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

[Esteban] scrisse:
(snip)
è forse l'algoritmo dello zaino?
--
Salutoni
Sergio
per rispondere... togli il group dall'indirizzo

 è forse l'algoritmo dello zaino?
In effetti forse farebbe meglio a cercare (sempre sul Sito Comune) "Best 
Fit Ordered"
Ciao

 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

 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