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

[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

[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

[Micoute]

Oui, bien sûr, mais je ne sais pas comment le faire !

[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 !

[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 !

[Shadow]

Ah ouais quand même

[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 '~'

[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.

[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

[Ar-S]

Le retour de la revanche de l'anagramme
Et oui, même si ce sont des chiffres, c'est un anagramme que tu souhaites faire.

[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

[falsam]

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

[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 ?

[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.

[falsam]

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.