PureBasic

Forums PureBasic - Français
http://forums.purebasic.com/french/

[Résolu] Permutation de groupes de caractères

http://forums.purebasic.com/french/viewtopic.php?t=15835

Page 1 sur 4

[Résolu] Permutation de groupes de caractères

Publié : lun. 22/févr./2016 17:43
par Micoute
Bonjour à tous,

sur le principe de mon code ci-joint, je voudrais faire permuter des groupes de caractères pas forcément de même longueurs du genre : "200~158~75~25" où les tildes séparent chaque groupes pour faire des suites du genre : 25~158~75~200, 158~25~75~200, 75~158~25~200, 200~158~75~25, etc...

Code : Tout sélectionner

BASE_PERM$="1234"   ;Régler la bases des Permutations

Debug "Permutations possibles de : " + BASE_PERM$

Dim COMPTEUR_PERM.l(Len(BASE_PERM$)+1)

While BASE_PERM$>""
  ;  MessageRequester("",BASE_PERM$)
  PERM$ = BASE_PERM$
  BASE$ = Left(BASE_PERM$,1) +"~"
  For i = 2 To Len(BASE_PERM$) - 1
    BASE$ + Mid(BASE_PERM$,i,1)+"~"
  Next i
  BASE$ + Right(BASE_PERM$,1)
  Debug BASE$
  Gosub PERMUTATION
Wend

End


;========== la Routine ==========
PERMUTATION:
  If POS_PERM.l=0
    COMPTEUR_PERM.l=0
    QUEUE_PERM$=""
    LONG_PERM.l = Len(BASE_PERM$)
  EndIf
  POS_PERM.l = 1
  NIVEAU_PERMUT:
  If COMPTEUR_PERM.l(POS_PERM.l)>=POS_PERM.l
    PERM_P.l = POS_PERM.l+1
    While Asc(QUEUE_PERM$)<PERM_P.l And QUEUE_PERM$>""
      POS_PERM.l = Asc(QUEUE_PERM$)
      QUEUE_PERM$ = Right(QUEUE_PERM$,Len(QUEUE_PERM$)-1)
      Gosub CHANGE_PERMUT
    Wend
    POS_PERM.l = PERM_P.l
    While PERM_P.l
      PERM_P.l = PERM_P.l-1
      COMPTEUR_PERM.l(PERM_P.l) = 0
    Wend
    If POS_PERM.l<LONG_PERM.l
      Goto NIVEAU_PERMUT
    EndIf
    BASE_PERM$=""
    POS_PERM.l=0
    Return
  EndIf
  Gosub CHANGE_PERMUT
  QUEUE_PERM$ = Chr(POS_PERM.l)+QUEUE_PERM$
  COMPTEUR_PERM.l(POS_PERM.l) = COMPTEUR_PERM.l(POS_PERM.l)+1
Return

CHANGE_PERMUT:
  BASE_PERM$ = Mid(BASE_PERM$,POS_PERM.l+1,1)+Left(BASE_PERM$,POS_PERM.l)+Right(BASE_PERM$,Len(BASE_PERM$)-(POS_PERM.l+1))
Return

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 17:58
par Shadow
Salut Micoute,

Tu veux calculer toutes les permutations des "Groupe" possible c'est ça ?

Ex:
Permutations possibles de : 125 ~ 214 ~ 38

125 ~ 214 ~ 38
214 ~ 125 ~ 38
38 ~ 125 ~ 214
125 ~ 38 ~ 214
214 ~ 38 ~ 125
38 ~ 214 ~ 125

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:00
par Micoute
Oui, bien sûr, mais je ne sais pas comment le faire !

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:04
par Shadow
Dis moi Micoute, combien de "Groupe" doit gérer ton algorithme ?
10, 100, 1000 ?

L'algo dois en gros calculer toutes les permutations
des dit "Groupe" si j'ai bien compris ?

Tu sais que plus y aura de groupe et plus se serra long !

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:09
par Micoute
Oui, bien entendu, mais en fait la limite, c'est la mémoire qui l'impose car elle n'est pas illimitée, sinon je pense qu'on pourrait aller jusqu'à plusieurs millions !

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:10
par Shadow
Ah ouais quand même :o

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:15
par Marc56
Je ne comprend pas grand chose en algo, mais dans ton exemple, il semble traiter "1234" comme une chaine de caractères (qu'il sépare en 4 caractères), donc pour ton souhait, c'est la même chose: tu découpe ta chaine en 4 éléments que tu met dans un tableau et tu utilises la même formule mais avec les éléments ().
Ça prendra autant de temps quelque soit la longueur des 4 éléments puisque tu ne travaille pas sur leur contenu mais sur leur identifiant.
Et encore moins si tu te sert de pointeurs (mais je n'ai jamais véritablement utilisé les pointeurs)

Stringfield() pour saucissonner la chaine sur les '~'

:wink:

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 18:34
par Micoute
Merci Marc56,

je travaille déjà sur ce système, mais je vais à l'aveugle, car mon exemple ne travaille qu'avec un seul caractère et le problème c'est que les groupes de caractères n'auront pas les mêmes longueurs.

Pour l'instant, je mets chaque groupe dans un tableau et je compte remplacer les nombres en indices de tableau.

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 19:03
par Micoute
Voici ma solution :

Code : Tout sélectionner

BASE_PERM$ = ""
Base_Groupe$ = "25~158~75~200"
Nb_Groupes = CountString(Base_Groupe$, "~") + 1

Global Dim tableau.s(Nb_Groupes - 1)
For i = 1 To Nb_Groupes
  tableau(i - 1) = StringField(Base_Groupe$, i, "~")
  BASE_PERM$ + Str(i)
Next i  

;BASE_PERM$="1234"   ;Régler la bases des Permutations

;Debug "Permutations possibles de : " + BASE_PERM$

Dim COMPTEUR_PERM.l(Len(BASE_PERM$)+1)

While BASE_PERM$>""
  ;  MessageRequester("",BASE_PERM$)
  PERM$ = BASE_PERM$
  BASE$ = tableau(Val(Left(BASE_PERM$,1))-1)+"~"
  For i = 2 To Len(BASE_PERM$) - 1
    BASE$ + tableau(Val(Mid(BASE_PERM$,i,1))-1)+"~"
  Next i
  BASE$ + tableau(Val(Right(BASE_PERM$,1))-1)
  Debug BASE$
  Gosub PERMUTATION
Wend

End


;========== la Routine ==========
PERMUTATION:
  If POS_PERM.l=0
    COMPTEUR_PERM.l=0
    QUEUE_PERM$=""
    LONG_PERM.l = Len(BASE_PERM$)
  EndIf
  POS_PERM.l = 1
  NIVEAU_PERMUT:
  If COMPTEUR_PERM.l(POS_PERM.l)>=POS_PERM.l
    PERM_P.l = POS_PERM.l+1
    While Asc(QUEUE_PERM$)<PERM_P.l And QUEUE_PERM$>""
      POS_PERM.l = Asc(QUEUE_PERM$)
      QUEUE_PERM$ = Right(QUEUE_PERM$,Len(QUEUE_PERM$)-1)
      Gosub CHANGE_PERMUT
    Wend
    POS_PERM.l = PERM_P.l
    While PERM_P.l
      PERM_P.l = PERM_P.l-1
      COMPTEUR_PERM.l(PERM_P.l) = 0
    Wend
    If POS_PERM.l<LONG_PERM.l
      Goto NIVEAU_PERMUT
    EndIf
    BASE_PERM$=""
    POS_PERM.l=0
    Return
  EndIf
  Gosub CHANGE_PERMUT
  QUEUE_PERM$ = Chr(POS_PERM.l)+QUEUE_PERM$
  COMPTEUR_PERM.l(POS_PERM.l) = COMPTEUR_PERM.l(POS_PERM.l)+1
Return

CHANGE_PERMUT:
  BASE_PERM$ = Mid(BASE_PERM$,POS_PERM.l+1,1)+Left(BASE_PERM$,POS_PERM.l)+Right(BASE_PERM$,Len(BASE_PERM$)-(POS_PERM.l+1))
Return

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 19:29
par Ar-S
Le retour de la revanche de l'anagramme :mrgreen:
Et oui, même si ce sont des chiffres, c'est un anagramme que tu souhaites faire.

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 19:35
par cage
Le nombre de combinaison possible est n! (factorielle de n)

Dans l'exemple donné, n vaut 4 (1234), c'est a dire 4 éléments a permuter.

Le nombre d'éléments est le même si on remplace (1234) par (6789) ou par (AGMT)

Le nombre de permutations possible est 4! soit 1*2*3*4 soit 24 combinaisons.

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,2,3,4
3,2,4,3
3,4,1,2
3,4,2,1
4,1,2,3
4,1,3,2
4,2,1,3
4,2,3,1
4,3,1,2
4,3,2,1

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 19:54
par falsam
cage a écrit :Le nombre de combinaison possible est n! (factorielle de n)

Dans l'exemple donné, n vaut 4 (1234), c'est a dire 4 éléments a permuter.

Le nombre d'éléments est le même si on remplace (1234) par (6789) ou par (AGMT)

Le nombre de permutations possible est 4! soit 1*2*3*4 soit 24 combinaisons.
Exactement Cage.

Il suffit d'utiliser un system de pattern correspondant au nombre d'éléments du groupe

Exemple : Le groupe "25~158~75~200" est composé de 4 éléments séparés par "~"

La pattern sera "1234"
1 Correspond à 25
2 Correspond à 158
3 Correspond à 75
4 Correspond à 200

Lors d'une permutation de pattern, si on obtient "2413"
alors nous aurons le résultat "158~200~25~75"

C'est ce que montre ce code : (Désactiver le support unicode dans les options de compilation)

Code : Tout sélectionner

;Désactiver le support unicode dans les options de compilation

Procedure.s SetPermutation(Pattern.s, n)
  Protected i, Factorial = 1, Temp
  
  For i = 2 To Len(Pattern)
    Factorial * (i - 1)
    Temp = PeekB(@Pattern + (i - ((n / Factorial) % i) - 1))
    PokeB(@Pattern + (i - ((n / Factorial) % i) - 1), PeekB(@Pattern + i - 1))
    PokeB(@Pattern + i - 1, Temp)
  Next
  
  ProcedureReturn Pattern
EndProcedure

Procedure GetCombination(Groupe.s)
  Protected i,j
  Protected Pattern.s       ;Composer d'une séquence de chiffres (Exemple : 1234)  
  Protected Permutation.s   ;Permutation retournée par la procédure SetPermutation. Exemple (2413)
  Protected Result.s        ;Résultat à afficher
  
  ;Compter le nombre de groupe
  ;Constituer le pattern correspondant (Exemple "25~158~75~200" donnera 1234)
  For i = 1 To CountString(Groupe, "~") + 1
    Pattern + Str(i)
  Next
  
  ;Générer les permutations pour la pattern
  i=1
  
  Repeat
    Result = ""
    Permutation = SetPermutation(Pattern, i)
    
    ;Construire le nouveau groupe en fonction de la pattern obtenue
    For j = 1 To Len(Permutation)
      Result + StringField(Groupe, Val(Mid(Permutation,j,1)), "~")+"~"
    Next
    
    ;Afficher le résultat
    Debug LSet(Result, Len(Result) - 1)
    
    ;Permutation suivante
    i + 1
  Until Permutation = Pattern
EndProcedure

;Donne les combinaison de ce groupe 
GetCombination("25~158~75~200")

;la pattern calculé sera "1234"
;1 correspond à 25
;2 correspond à 158
;3 correspond à 75
;4 correspond à 200

;Lors d'une permutation de pattern, si on obtient "2413"
;alors nous aurons le résultat "158~200~25~75"
Ref : http://forum.purebasic.com/english/view ... 42#p208106

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 20:27
par Shadow
Attention, ça ne fonctionne pas toujours !
Essai avec ceci par exemple: 5~16~20~29~62~75~136~167~175~219

Il ne faut pas être limité à X groupe.
Micoute a dis que il pourrais y avoir des millions de groupe.

Perso ça me parait tout de même plus qu'énorme, aucun ordi ne peut calculer ça ?

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 20:30
par Micoute
Merci pour toutes vos réponses, le problème c'est qu'on est limité à 10 dimensions, parce qu'à la ligne 25 on a Pattern + Str(i), donc jusqu'à 9 il n'y a qu'un caractère.

Re: Permutation de groupes de caractères

Publié : lun. 22/févr./2016 20:36
par falsam
Shadow a écrit :Attention, ça ne fonctionne pas toujours !
Essai avec ceci par exemple: 5~16~20~29~62~75~136~167~175~219
là c'est normal car chaque composant de la pattern est composé des chiffre 1 à 9.

Avec ton exemple on a 10 composants pour un groupe. Donc ça ne fonctionne pas.

Est ce que Micoute à des groupes avec plus de 9 composants ? A lui de le dire.

L'autre solution est de passer par les lettres de l'alphabet.
Fuseau horaire sur UTC+01:00
Page 1 sur 4

Développé par phpBB® Forum Software © phpBB Limited

Traduction française officielle © Qiaeru