Sujet Précédent Sujet Suivant

Permutation binaire de longueur n et k bits

Résolu
FunMagic Messages postés 4 Date d'inscription mardi 8 juin 2010 Statut Membre Dernière intervention 12 juillet 2010 - 8 juin 2010 à 12:07
FunMagic Messages postés 4 Date d'inscription mardi 8 juin 2010 Statut Membre Dernière intervention 12 juillet 2010 - 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é :-)

6 réponses

Réponse 1 / 6
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 57
8 juin 2010 à 21:55
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
3
Réponse 2 / 6
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 57
9 juin 2010 à 16:55
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 ?
3
Réponse 3 / 6
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 57
8 juin 2010 à 17:39
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
0
Réponse 4 / 6
cs_ShayW Messages postés 3253 Date d'inscription jeudi 26 novembre 2009 Statut Membre Dernière intervention 3 décembre 2019 57
8 juin 2010 à 18:37
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
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 6
FunMagic Messages postés 4 Date d'inscription mardi 8 juin 2010 Statut Membre Dernière intervention 12 juillet 2010
9 juin 2010 à 14:09
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 ! :-)
0
Réponse 6 / 6
FunMagic Messages postés 4 Date d'inscription mardi 8 juin 2010 Statut Membre Dernière intervention 12 juillet 2010
10 juin 2010 à 01:34
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
0

Discussions similaires

Fonction permutation?
thguillon -
thguillon -

3 réponses
Permutation d'images
lgrenon -
derradjiaribi -

3 réponses
Permuter 2 labels
l337sanders -
Benouille -

3 réponses
Permutation aléatoire d'un ensemble de nombre hexa
faresayed -
cptpingu -

3 réponses
Permutation
Ombitious_Developper -
Stepharcher -

2 réponses
Rejoignez-nous