domenica 30 ottobre 2011

[VB6] Combinazioni Semplici e con Ripetizione

Descrizione :
Due Function di mia "invenzione" per il calcolo delle Combinazioni con e senza Ripetizione.

+ Articolo :

1. Combinazioni semplici ( senza ripetizioni ) :
Si chiama combinazione semplice una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti e non si può ripetere lo stesso elemento più volte.

arrayElementi è l'Array degli N elementi dell'insieme S di partenza.
Faccio notare che tale Array è di tipo Variant, e che la mia Function può operare su Array di svariati tipi, quindi Integer, String, Char, ecc...
dimensioneGruppo indica il numero di elementi da prendere in ogni Combinazione generata.

--> La Function :

Public Function CombinazioniSemplici(ByVal arrayElementi As Variant, ByVal dimensioneGruppo As Byte) As Collection
 
    Dim LC As New Collection
    If UBound(arrayElementi) = 0 Then
        Set CombinazioniSemplici = LC
    End If
    If dimensioneGruppo = 0 Or dimensioneGruppo > UBound(arrayElementi) Then
        Set CombinazioniSemplici = LC
    End If
    Dim aP() As Integer
    ReDim aP(dimensioneGruppo - 1)
    Dim i As Integer
    For i = 0 To UBound(aP)
        aP(i) = i
    Next i
    Dim j As Integer
    Dim C As String
    Dim cnt As Integer
    Do
        C = ""
        For i = 0 To UBound(aP)
            C = C & arrayElementi(aP(i))
        Next i
        LC.Add (C)
 
        cnt = 0
        For i = UBound(aP) To 0 Step -1
            If aP(i) = UBound(arrayElementi) - cnt Then
                cnt = cnt + 1
                If cnt = UBound(aP) + 1 Then Exit Do
            Else
                aP(i) = aP(i) + 1
                For j = 0 To UBound(aP)
                    If i < j Then aP(j) = aP(i) + (j - i)
                Next
                Exit For
            End If
        Next i
    Loop
 
    Set CombinazioniSemplici = LC
 
End Function

--> Un Esempio di Utilizzo ( Output su ListBox ) :
    List1.Clear
 
    Dim N() As Variant
    N = Array("a", "b", "c", "d")
    Dim K As Byte
    K = 3
 
    Dim Comb As Collection
    Set Comb = CombinazioniSemplici(N, K)
 
    Dim i As Integer
    For i = 1 To Comb.Count
        List1.AddItem (Comb(i))
    Next i
 
    MsgBox "Numero combinazioni generate = " & Comb.Count


2. Combinazioni con Ripetizione :
Quando l'ordine non è importante ma è possibile avere componenti ripetute si parla di combinazioni con ripetizione. Il numero di combinazioni con ripetizione di N oggetti di classe K è uguale a quello delle combinazioni senza ripetizione di N + K - 1 oggetti di classe K.

arrayElementi è l'Array degli N elementi dell'insieme S di partenza.
Anche qui l'Array è di tipo Variant, e la mia Function può operare su Array di svariati tipi, quindi Integer, String, Char, ecc...
classe indica il numero di elementi da prendere in ogni Combinazione generata.

--> La Function :

Public Function CombinazioniConRipetizione(ByVal arrayElementi As Variant, ByVal classe As Byte) As Collection
 
    Dim LC As New Collection
    If UBound(arrayElementi) = 0 Then
        Set CombinazioniConRipetizione = LC
    End If
    If classe = 0 Then
        Set CombinazioniConRipetizione = LC
    End If
    Dim aP() As Integer
    ReDim aP(classe - 1)
    Dim i As Integer
    Dim j As Integer
    Dim C As String
    Dim cnt As Integer
    Do
        C = ""
        For i = 0 To UBound(aP)
            C = C & arrayElementi(aP(i))
        Next i
        LC.Add (C)
 
        cnt = 0
        For i = UBound(aP) To 0 Step -1
            If aP(i) = UBound(arrayElementi) Then
                cnt = cnt + 1
                If cnt = UBound(aP) + 1 Then Exit Do
            Else
                aP(i) = aP(i) + 1
                For j = 0 To UBound(aP)
                    If i < j Then aP(j) = aP(i)
                Next
                Exit For
            End If
        Next i
    Loop
 
    Set CombinazioniConRipetizione = LC
 
End Function 

--> Un Esempio di Utilizzo ( Output su ListBox ) :
    List1.Clear
 
    Dim N() As Variant
    N = Array("a", "b", "c", "d")
    Dim K As Byte
    K = 3
 
    Dim Comb As Collection
    Set Comb = CombinazioniConRipetizione(N, K)
 
    Dim i As Integer
    For i = 1 To Comb.Count
        List1.AddItem (Comb(i))
    Next i
 
    MsgBox "Numero combinazioni generate = " & Comb.Count

+ Fine Articolo.


Un Click su "Mi Piace" è il modo migliore per ringraziare l'autore di questo articolo.




1 commenti:

lupoblu ha detto...

Devo capire megli come funziona, ma mi sembra una soluzione molto elegante

Mi chiedevo se mi riuscivi ad aiutare a risolvere un CASO UN PO' PIU' COMPLESSO.
TROVARE GRUPPI DI COMBINAZIONI SEMPLICI INDIPENDENTI
Ad esempio se sono 35 le combinazioni semplici di 7 elementi di classe 3, diventano 70 le "coppie" di terne indipendenti come ad esempio:
(1,2,3) (4,5,6)
(1,2,3) (4,5,7)
(1,2,3) (4,6,7)
(1,2,3) (5,6,7)
(1,2,4) (3,5,6)
...
In realtà poi non avrei finito perché dovrei trasformare gli elemnti delle "coppie" di classe k trovate in numeri binari, sommare gli elementi in tutti i modi posssibili come se fossero numeri decimali e trovare quelle coppie che mi danno sempre somme differenti ...
Ma già risolvere la prima parte COMBINATORIA mi SAREBBE DI ENORME AIUTO ;-)

SPERO IN QUALCHE VOSTRO AIUTO

Posta un commento

Favorites Twitter Facebook Delicious Digg Stumbleupon More

 
Design by Free WordPress Themes Modificato da MarcoGG