|
|
|
|
Strumenti |
13-10-2017, 10:16 | #1 |
Senior Member
Iscritto dal: Jan 2006
Messaggi: 748
|
[VB]Calcolo combinazioni in una matrice binaria. Cerco maggiore efficienza
Sto cercando di creare uno script che calcoli il numero di combinazioni possibili in una matrice binaria (ad esempio 6x6 o anche più grande) che soddisfi (come unico dato noto) una determinata somma di ciascuna riga e di ciascuna colonna. (ogni riga e ogni colonna possono avere anche somme differenti)
Per esempio, una matrice binaria 3x3 in cui la somma di ciascuna riga e di ciascuna colonna è sempre 1 le risultanti matrici saranno: |0|0|1| |0|1|0| |1|0|0| poi |0|0|1| |1|0|0| |0|1|0| poi |0|1|0| |1|0|0| |0|0|1| poi |0|1|0| |0|0|1| |1|0|0| poi |1|0|0| |0|1|0| |0|0|1| e infine |1|0|0| |0|0|1| |0|1|0| Quindi in tutto sono 6 A me non interessa vedere le matrici riempite, ma solo contare quante combinazioni sono possibili. In VisualBasic questo script lo fa, ma in maniera forse poco efficiente (va ad occuparmi al massimo il 20% della cpu). Inoltre pensavo che mi mostrasse il numero progressivo della combinazione trovata man mano in tempo reale, e invece mostra tali numeri solo alla fine dell'esecuzione, quando ormai vedo già anche il numero finale.. Questo esempio è per calcolare una matrice di ordine 6 in cui la somma in ciascuna riga e in ciascuna colonna è sempre 3 Codice:
Module Module1 Sub Main() Dim ct As Integer ct = 0 Dim a(35) For a0 = 0 To 1 For a1 = 0 To 1 For a2 = 0 To 1 For a3 = 0 To 1 For a4 = 0 To 1 For a5 = 0 To 1 For a6 = 0 To 1 For a7 = 0 To 1 For a8 = 0 To 1 For a9 = 0 To 1 For a10 = 0 To 1 For a11 = 0 To 1 For a12 = 0 To 1 For a13 = 0 To 1 For a14 = 0 To 1 For a15 = 0 To 1 For a16 = 0 To 1 For a17 = 0 To 1 For a18 = 0 To 1 For a19 = 0 To 1 For a20 = 0 To 1 For a21 = 0 To 1 For a22 = 0 To 1 For a23 = 0 To 1 For a24 = 0 To 1 For a25 = 0 To 1 For a26 = 0 To 1 For a27 = 0 To 1 For a28 = 0 To 1 For a29 = 0 To 1 For a30 = 0 To 1 For a31 = 0 To 1 For a32 = 0 To 1 For a33 = 0 To 1 For a34 = 0 To 1 For a35 = 0 To 1 If (a0 + a1 + a2 + a3 + a4 + a5 = 3 And a6 + a7 + a8 + a9 + a10 + a11 = 3 And a12 + a13 + a14 + a15 + a16 + a17 = 3 And a18 + a19 + a20 + a21 + a22 + a23 = 3 And a24 + a25 + a26 + a27 + a28 + a29 = 3 And a30 + a31 + a32 + a33 + a34 + a35 = 3 And a0 + a6 + a12 + a18 + a24 + a30 = 3 And a1 + a7 + a13 + a19 + a25 + a31 = 3 And a2 + a8 + a14 + a20 + a26 + a32 = 3 And a3 + a9 + a15 + a21 + a27 + a33 = 3 And a4 + a10 + a16 + a22 + a28 + a34 = 3 And a5 + a11 + a17 + a23 + a29 + a35 = 3) Then ct = ct + 1 Debug.Print(ct) End If Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Next Debug.Print(ct) End Sub End Module Tenete conto che non so programmare Grazie
__________________
I miei oggetti in vendita: il mio sito web 1e2.it Ultimi affari con: GByTe87 MiTiSi siluro85 DDA Eagle_76 DraculaV-V glm2006ITALY mokabo |
15-10-2017, 20:23 | #2 |
Senior Member
Iscritto dal: Aug 2017
Messaggi: 469
|
Era evidente vedendo quel cuneo gigante nel tuo codice
Ti consiglio di leggere https://it.wikipedia.org/wiki/Algoritmo_ricorsivo il concetto è definire una funzione parametrica e richiamarla da se stessa... |
16-10-2017, 09:43 | #3 |
Senior Member
Iscritto dal: Jan 2006
Messaggi: 748
|
Eh, ma per questo chiedevo qui... Ho provato a leggere quella pagina che mi hai linkato ma non capisco nemmeno se possa essere applicabile o meno al mio caso in quanto alla fine del cuneo ci sono delle operazioni di somma che richiedono la distinzione di ciascuna cella della matrice.
Comunque quello che vorrei fare per ottimizzare il calcolo è procedere in questo modo: anziché vagliare tutte le soluzioni contando in maniera bruta da 0 a n (perché se stendo una matrice di ordine 3 viene fuori un numero binario a 9 cifre, quindi quello che faccio ora non è altro che testare tutte le combinazioni partendo da 000000000 a 111111111), potrei invece iniziare a verificare quali combinazioni soddisfano il criterio di somma della prima riga, e a quel punto testare poi solo quelle combinazioni trovate con la prima colonna e trovare quelle che soddisfano il criterio di somma della prima colonna; dopodiché si passa alla seconda riga, partendo però dalla seconda cella trovando quelle combinazioni che soddisfano i criteri e sono coerenti con le soluzioni trovate della prima riga e della prima colonna. Poi si passa al completamento della seconda colonna e così via. Provo a esemplificare. Parto da una matrice binaria di ordine 3. Cerco tutte le combinazioni in cui la somma di ogni riga e di ogni colonna è sempre 2. Dunque procedo verificando le combinazioni della prima riga che saranno: 110, poi 101 e infine 011. Ora verifico, partendo da queste tre combinazioni, quali soddisfano il criterio della prima colonna. Quindi: Codice:
110 1 0 Codice:
110 0 1 Codice:
101 1 0 Codice:
101 0 1 Codice:
011 1 1 Codice:
110 110 0 Codice:
110 011 1 Codice:
110 101 0 In una grande matrice questo però comporterebbe, credo, il fatto di dover tenere sempre in memoria ciascuna delle soluzioni identificate per ogni riga e colonna. E in una matrice di ordine 6 ci sono circa 290 mila combinazioni massime se si usa come criterio la somma pari a 3 per ciascuna riga e colonna. In una matrice di ordine maggiore questo numero massimo di combinazioni sale a dismisura! Per questo vorrei ottimizzare la ricerca e testare il codice... però mi serve un aiuto a creare il codice
__________________
I miei oggetti in vendita: il mio sito web 1e2.it Ultimi affari con: GByTe87 MiTiSi siluro85 DDA Eagle_76 DraculaV-V glm2006ITALY mokabo |
16-10-2017, 16:28 | #4 |
Junior Member
Iscritto dal: Oct 2017
Messaggi: 9
|
se lo scopo del programma è restituire solo il numero di combinazioni basta usare una formula,con qualche prova direi che per una matrice n*n il numero di combinazioni binarie con colonne e righe a somma 1 è n! (fattoriale...).
Spero si capisca cosa intendo, magari un matematico potrebbe illuminarci sul calcolo combinatorio. |
16-10-2017, 16:40 | #5 |
Senior Member
Iscritto dal: Jan 2006
Messaggi: 748
|
Vero, può essere, anche se la formula dovrebbe tenere conto del fatto che io potrei voler sapere quante combinazioni ci sono avendo somme tutte diverse per riga e colonna...
Esempio, matrice di ordine 7, la prima riga ha una somma di 4, la seconda riga ha somma 7, la terza riga ha somma 2 e così via... per cui non sarebbe tutto poi molto lineare. Però non è detto che non si possa con una formula matematica
__________________
I miei oggetti in vendita: il mio sito web 1e2.it Ultimi affari con: GByTe87 MiTiSi siluro85 DDA Eagle_76 DraculaV-V glm2006ITALY mokabo |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 01:54.