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

FunMagic 4 Messages postés mardi 8 juin 2010Date d'inscription 12 juillet 2010 Dernière intervention - 8 juin 2010 à 12:07 - Dernière réponse : FunMagic 4 Messages postés mardi 8 juin 2010Date d'inscription 12 juillet 2010 Dernière intervention
- 10 juin 2010 à 01:34
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é :-)
Afficher la suite 

Votre réponse

6 réponses

cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 8 juin 2010 à 21:55
+3
Utile
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
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_ShayW
cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 9 juin 2010 à 16:55
+3
Utile
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 ?
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_ShayW
cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 8 juin 2010 à 17:39
0
Utile
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
Commenter la réponse de cs_ShayW
cs_ShayW 3238 Messages postés jeudi 26 novembre 2009Date d'inscription 14 mars 2018 Dernière intervention - 8 juin 2010 à 18:37
0
Utile
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
Commenter la réponse de cs_ShayW
FunMagic 4 Messages postés mardi 8 juin 2010Date d'inscription 12 juillet 2010 Dernière intervention - 9 juin 2010 à 14:09
0
Utile
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 ! :-)
Commenter la réponse de FunMagic
FunMagic 4 Messages postés mardi 8 juin 2010Date d'inscription 12 juillet 2010 Dernière intervention - 10 juin 2010 à 01:34
0
Utile
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
Commenter la réponse de FunMagic

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.