Permutation binaire de longueur n et k bits [Résolu]

Signaler
Messages postés
4
Date d'inscription
mardi 8 juin 2010
Statut
Membre
Dernière intervention
12 juillet 2010
-
Messages postés
4
Date d'inscription
mardi 8 juin 2010
Statut
Membre
Dernière intervention
12 juillet 2010
-
Bonjour, :-)

Je me permet de chercher de l'aide, car je n'arrive pas à trouver la solution pour un algorithme de permutation qui me donne toute les solutions sans répétition d'une chaine de longueur n qui contient k bits:
Par exemple if n=4 et k=3 il y a:

0111
1011
1101
1110

J'ai besoin de trouver le meilleures chemin pour générer cette algorithme en VBA ou VB.(récursif ou pas ) :-)

Merci pour tout aide apporté :-)

6 réponses

Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
50
Salut
Je corrige un bug
Private Sub permutation()
        Dim binary As String
        Dim number As Long
        Dim startnum As Long
        Dim beginnum As String
        Dim digitpos As Long
        Dim countdigit As Long
        Dim pos As Long
        Dim permut() As String
        Dim countpermut As Long
        Dim n As Long
        Dim k As Long
        n = 22
        k = 6
        countpermut = 0

        startnum = startnum.ToString.PadLeft(k + 1, "1"c)
        beginnum = Str(startnum)
        beginnum = Trim(Mid(beginnum, 1, Len(beginnum) - 1))
        startnum = Convert.ToInt32(beginnum, 2)

        For number = startnum To 2 ^ n
            binary = Convert.ToString(number, 2)

            If Len(binary) >= k Then
                'au moins que binary a k chiffres
                countdigit = 0
                'compte les "1" dans binary
                For pos = 1 To Len(binary)
                    digitpos = InStr(pos, binary, "1", CompareMethod.Text)
                    If digitpos = pos Then
                        countdigit = countdigit + 1
                    End If
                Next
                If countdigit = k Then
                    'ajoutes les "0" devant
                    If Len(binary) < n Then
                        binary = binary.ToString.PadLeft(n, "0"c)
                    End If
                    ReDim Preserve permut(countpermut)
                    permut(countpermut) = binary
                    countpermut = countpermut + 1
                End If

            End If
        Next
        

    End Sub
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
50
Salut
Le problème en vb6 le code ne marche pas alors
ou il faut écrire les fontctions soi meme
voila le code pour vb6 il est plus long
Private Sub permutation()
        Dim binary As String
        Dim prefix As String
        Dim number As Long
        Dim startnum As Long
        Dim iter As Integer
        Dim beginnum As String
        Dim digitpos As Long
        Dim countdigit As Long
        Dim pos As Long
        Dim permut() As String
        Dim countpermut As Long
        Dim n As Long
        Dim k As Long
        n = 6
        k = 3
        countpermut = 0
       
 'calcul du plus petit nombre binaire formé de 
' k 1 par ex si k 5 donc 11111 binaire 31
' ou 32 -1 donc 2^5 - 1 

       startnum = 2 ^ k - 1
     
        For number = startnum To 2 ^ n
           binary = GetBinary(number)
           

            If Len(binary) >= k Then
                'au moins que binary a k chiffres
                countdigit = 0
                'compte les "1" dans binary
                For pos = 1 To Len(binary)
                    digitpos = InStr(pos, binary, "1", 1)
                    If digitpos = pos Then
                        countdigit = countdigit + 1
                    End If
                Next
                If countdigit = k Then
                    'ajoutes les "0" devant
                    prefix = ""
                    If Len(binary) < n Then
                       For iter = 0 To n - Len(binary) - 1
                        prefix = prefix & "0"
                       Next
                    End If
                    binary = prefix & binary
                    ReDim Preserve permut(countpermut)
                    permut(countpermut) = binary
                    countpermut = countpermut + 1
                End If

            End If
        Next
        

    End Sub


 Private Function GetBinary(ByVal number As Long) As String
'conversion en binaire 
 Dim mybinary As String
  mybinary = ""
 While number > 0
  mybinary = mybinary & number Mod 2
   number = number \ 2
 Wend
  GetBinary = StrReverse(mybinary)
End Function


Bonne chance
C'est pourquoi l'algorithm ?
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
50
Salut
Private Sub permutation()
        Dim binary As String
        Dim number As Integer
        Dim digitpos As Integer
        Dim countdigit As Integer
        Dim pos As Integer
        Dim permut() As String
        Dim countpermut As Integer
        Dim n As Integer
        Dim k As Integer
        n = 6
        k = 3
        countpermut = 0
        ' loop sur tous les nombres binaires de n chiffre
        For number = 0 To 2 ^ n
            binary = Convert.ToString(number, 2)

            If Len(binary) >= k Then
                'au moins que binary a k chiffres
                countdigit = 0
                'compte les "1" dans binary
                For pos = 1 To Len(binary)
                    digitpos = InStr(pos, binary, "1", CompareMethod.Text)
                    If digitpos = pos Then
                        countdigit = countdigit + 1
                    End If
                Next
                If countdigit = k Then
                    'ajoutes les "0" devant
                    If Len(binary) < n Then
                        binary = binary.ToString.PadLeft(n, "0"c)
                    End If
                    ReDim Preserve permut(countpermut)
                    permut(countpermut) = binary
                    countpermut = countpermut + 1
                End If

            End If
        Next
    End Sub



J'espère que ça ira
Messages postés
3258
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
3 décembre 2019
50
j'améliore
Private Sub permutation()
        Dim binary As String
        Dim number As Long
        Dim startnum As Long
        Dim beginnum As String
        Dim digitpos As Long
        Dim countdigit As Long
        Dim pos As Long
        Dim permut() As String
        Dim countpermut As Long
        Dim n As Long
        Dim k As Long
        n = 20
        k = 6
        countpermut = 0
        ' loop sur tous les nombres binaires de n chiffre 
        startnum = startnum.ToString.PadLeft(k, "1"c)
        beginnum = Str(startnum)
        beginnum = Mid(beginnum, 1, Len(beginnum) - 1)
        beginnum = Convert.ToInt32(beginnum)
        For number = beginnum To 2 ^ n
            binary = Convert.ToString(number, 2)

            If Len(binary) >= k Then
                'au moins que binary a k chiffres
                countdigit = 0
                'compte les "1" dans binary
                For pos = 1 To Len(binary)
                    digitpos = InStr(pos, binary, "1", CompareMethod.Text)
                    If digitpos = pos Then
                        countdigit = countdigit + 1
                    End If
                Next
                If countdigit = k Then
                    'ajoutes les "0" devant
                    If Len(binary) < n Then
                        binary = binary.ToString.PadLeft(n, "0"c)
                    End If
                    ReDim Preserve permut(countpermut)
                    permut(countpermut) = binary
                    countpermut = countpermut + 1
                End If

            End If
        Next
        

    End Sub
Messages postés
4
Date d'inscription
mardi 8 juin 2010
Statut
Membre
Dernière intervention
12 juillet 2010

Merci ShayW !

J'avoue que pour moi j'ai eu de la peine à concevoir ce type d'algo ! Dans tout les cas je te remercie pour ton aide !

Juste une petite question ! J'utilise VB6 et la ligne:
startnum = startnum.ToString.PadLeft(k + 1, "1"c)
et
binary = binary.ToString.PadLeft(n, "0"c)
n'est pas reconnue !:-(
Pourrais-tu juste m'éclairer pour que je puisse ajuster mon code :-)

Avec tout mes remerciment ! :-)
Messages postés
4
Date d'inscription
mardi 8 juin 2010
Statut
Membre
Dernière intervention
12 juillet 2010

Vraiment un grand merci !! :-)

De mon coté j'ai essayé à ma façon de modifier certains algo que j'ai trouvé sur le net mais sans trop de succès. J'avais presque réussi en utilisant un autre algo de permuation.. bien que le code étais extrêment court ( algo récursif) il était extrêmement lent !

Celui que tu viens de me faire TipTop et rapide !
Je te remercie encore.. je vais pouvoir continuer le développement de mon idée.

J'ai besoin de cette algo pour faire une comparaison entre différente suite de dénombrement.. J'essaye de développer un nouvel algo de comparaison.

Big thanks :-) All is ok