[VB]Calcolo combinazioni in una matrice binaria. Cerco maggiore efficienza

[galerio]

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

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

Come posso migliorare il codice, sfuttare appieno il processore e tutti i suoi core e visualizzare il numero di combinazioni trovate in tempo rale durante l'esecuzione?

Tenete conto che non so programmare :p

Grazie

[Mursey]

Tenete conto che non so programmare

Era evidente vedendo quel cuneo gigante nel tuo codice :D

Ti consiglio di leggere https://it.wikipedia.org/wiki/Algoritmo_ricorsivo
il concetto è definire una funzione parametrica e richiamarla da se stessa...

[galerio]

Eh, ma per questo chiedevo qui... Ho provato a leggere quella pagina che mi hai linkato ma :wtf: :mbe: :confused: 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:
110
1
0
poi
110
0
1
con la seconda combinazione invece:
101
1
0
101
0
1
e con la terza combinazione di riga ho solo
011
1
1
A questo punto verifico la seconda riga, partendo dalla seconda cella perché la prima è già stata testata poco fa. Quindi:

110
110
0
poi
110
011
1
110
101
0

etc etc cosicché man mano che si procede il numero di combinazioni da trovare sarà sempre meno in quanto diminuisce il numero di celle da testare.


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

[SimoneR95]

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.

[galerio]

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