Algorithme de combinaison de chaines caractere (genre knapsack)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 385 fois - Téléchargée 28 fois

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

Ajouter un commentaire Commentaires
RAPTISTA Messages postés 6 Date d'inscription mardi 27 mars 2007 Statut Membre Dernière intervention 8 juin 2007
8 juin 2007 à 16:43
Toi aussi t'es genial
nizar77 Messages postés 1 Date d'inscription dimanche 28 mars 2004 Statut Membre Dernière intervention 22 décembre 2010
14 mai 2007 à 11:41
bonjour , je trouve votre code tres interessant ,
mais j'ai une diffuculter pour le transformer en c#

pouvez - vous m'aider

merci
cs_miss fafa Messages postés 46 Date d'inscription mercredi 4 avril 2007 Statut Membre Dernière intervention 25 février 2009
29 avril 2007 à 11:38
bjr tt le monde moi j'ai des problemes en algorithme
moi je vx ecrire un algo qui permet de changer 1 expression mathematique simple en notation de post fixe
merci en avance @++
mon msn est assia_123456_@hotmail.com
si qlq vx m'aider invite moi et merci en avance
cs_ikrama Messages postés 1 Date d'inscription mardi 25 avril 2006 Statut Membre Dernière intervention 14 février 2007
14 févr. 2007 à 16:54
Bonjour,
j'aurais besoin de ces deux algorithmes SVP :
1.un algorithme qui affiche les nombres impaires existant entre 1 et n

2.un algorithme qui calcule la somme des chiffres d'un nombre entier : N = A n A m -1
A ----> S= Ao + A 1 +.....+A n

et merciiiii
ik.
Drikce06 Messages postés 2237 Date d'inscription lundi 29 mai 2006 Statut Membre Dernière intervention 29 mai 2008 11
15 déc. 2006 à 11:08
Salut, ce serai bien de passer la chaine de caractère en paramètre dans la l'appel de la procédure!

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.