Algorithme de combinaison de chaines caractere (genre knapsack)

Commenter

Contenu du snippet

SUITE MESSAGE POSTE SUR FORUM http://www.vbfrance.com/infomsg_COMBINAISON-CHAINE-CARACTERES_859397.aspx#1

Bonjour à tous,

Dans mon projet informatique fait en vb 2005, je dois proposer à l'utilisateur tous les combinaisons possible a partir d'une chaine de caractères. Je m'explique, avec un exemple (ce sera plus comprehensible)

Chaine de départ : "forum vbfrance est genial"

ca doit me retourner (pas forcement dans cet ordre)

forum vbfrance est genial
forum vbfrance est
forum vbfrance genial
forum est genial
vbfrance est genial
forum vbfrance
forum est
forum genial
vbfrance est
vbfrance genial
est genial
forum
vbfrance
est
genial

avec les contraintes sont les suivantes :
- la chaine de depart peut etre constitue de N mots
- mot identifié par un espace
- ordre des mots doit etre respecté (cad dans l'exemple : genial vbfrance est forum >>> pas possible)

Source / Exemple : 


Private Sub remplissageComboClient()
        cmbClient.Items.Clear()

        Dim sTabMots() As String = Split(GsNomClient)
        Dim iNbMots As Integer = sTabMots.Length
        Dim oPile As New Generic.Stack(Of String)
        Dim arrlstATrie As New ArrayList
        Dim k, iPuissanceCourante As Integer
        Dim sChaineFinal As String = ""

        Dim iTabPuissance2(iNbMots - 1) As Integer

        'remplissage du tableau des puissances de 2 en fonctions du nombre de mots
        For i As Integer = 0 To iNbMots - 1
            iTabPuissance2(i) = CInt(Math.Pow(2, i))
        Next

        ' parcours toutes les combinaison de puissance de 2 possibles avec un max a 2^mots - 1
        For i As Integer = CInt(Math.Pow(2, iNbMots) - 1) To 1 Step -1
            iPuissanceCourante = i
            k = iNbMots - 1
            While iPuissanceCourante > 0 AndAlso k >= 0
                If iPuissanceCourante >= iTabPuissance2(k) Then
                    iPuissanceCourante -= iTabPuissance2(k)
                    'stockage dans une pile pour beneficier du "LIFO" ou "FILO"
                    oPile.Push(sTabMots(k) & " ")
                End If
                k -= 1
            End While

            'inversion des mots pour respecter l'ordre de la chaine d'entree 
            ' on depile
            sChaineFinal = ""
            While oPile.Count > 0
                sChaineFinal &= CStr(oPile.Pop)
            End While
            sChaineFinal = FrameWork.Chaine.suppressionEspacesDeFin(sChaineFinal)

            If sChaineFinal <> "" Then
                ' petite astuce pour avoir un affichage correct cad de la plus grande a la plus petite chaine
                ' on stocke le nombre de car. de la chaine
                arrlstATrie.Add(Format(sChaineFinal.Length, "0000") & "#" & sChaineFinal)
            End If
            sChaineFinal = ""
            oPile.Clear()
        Next

        'on trie la list (plus petit au plus grand)
        arrlstATrie.Sort()
        'on inverse le tri (plus grand au plus petit)
        arrlstATrie.Reverse()

        'ajout des autres combinaisons
        For i As Integer = 0 To arrlstATrie.Count - 1
            Dim sTab() As String = Split(CStr(arrlstATrie.Item(i)), "#")
            cmbClient.Items.Add(sTab(1))
        Next
        cmbClient.MaxDropDownItems = FrameWork.Constantes.AFF_COMBO_MAX

        arrlstATrie = Nothing
        oPile = Nothing
    End Sub

Conclusion :


Je suis ouvert a toutes optimisations et/ou critiques (c comme cela qu'on progresse)

A voir également

S'inscrire maintenant

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.