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 4 sur 4

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

Publié : lun. 29/févr./2016 21:02
par falsam
Moi aussi je l'ai dit :mrgreen:

Allez on boucle http://www.purebasic.fr/french/viewtopi ... 42#p181042

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

Publié : lun. 29/févr./2016 21:25
par falsam
Puisque vous insistez je vais jouer avec vous.

■ Code à compiler sans la prise en charge unicode.

■ Objectif.
Connaitre le nombre de permutations pour un tirage.
Exemple : La combinaison Cube.Plane.Sphere.Cylinder est extraite de 24 combinaisons possibles.

Connaitre le nombre de permutations pour arriver à un tirage
Exemple : Il a fallu 8 permutations pour arriver à la combinaison Cube.Plane.Sphere.Cylinder
Bien évidement ce calcul est dépendant de mon algorithme.

Code : Tout sélectionner

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

Global CountGroup, Result.s

;Split() permet de diviser une chaîne de caractères à partir d'un séparateur pour fournir un tableau de sous-chaînes.
;Cette fonctionnalité existe en JavaScript.
Procedure Split(Array Array.s(1), String.s, Delimiter.s)
  Protected File, i, j, Buffer.s
  
  j = CountString(String, Delimiter)  
  ReDim Array(j)
  For i=1 To j+1  
    Array(i-1) = StringField(String, i, Delimiter)
  Next
EndProcedure

;De quoi calculer le nombre de permutations possibles
Procedure.q Factoriel(n.q) 
  If n=0
    ProcedureReturn #True
  Else
    ProcedureReturn n*Factoriel(n-1)
  EndIf
EndProcedure 

;Générer une permutation
Procedure.s SetPermutation(Pattern.s, n)
  Protected i, Factorial = 1, Temp
  
  For i = 2 To Len(Pattern)
    Factorial * (i - 1) 
    *n1.Byte = @Pattern + (i - ((n / Factorial) % i) - 1) 
    *n2.Byte = @Pattern + i - 1 
    Temp = *n1\b 
    *n1\b = *n2\b 
    *n2\b = Temp   
  Next
  
  ProcedureReturn Pattern
EndProcedure

;Combien de permutations possibles pour la combinaison passée en paramétre
Procedure GetPermutation(Combination.s, Delimitator.s)
  Protected i,j
  Protected Pattern.s             ;Composer d'une séquence de chiffres (Exemple : ABCD)  
  Protected Permutation.s         ;Permutation retournée par la procédure SetPermutation. Exemple (BDAC)
  Protected Dim Combination.s(0)  ;Trie du paramétre Combination
  Protected MemCombination.s      ;Mémorise le paramétre Combination passé en paramétre
  Protected MemPattern.s          ;Mémorise la pattern de travail correspondant à Combination
  
  ;0 - Affiche le nombre de combinaisons possibles pour la combinaison passée en paramétre. 
  Debug "La combinaison " + Combination + " est extraite de " + Factoriel(CountString(Combination, Delimitator) + 1) + " combinaisons possibles." + #CRLF$ 
  
  ;1 - Mémorisation de la combinaison passé en paramétre
  MemCombination = Combination
  
  ;2 - Tri de la combinaison à l'aide d'un tableau
  Split(Combination(), Combination, ".")
  SortArray(Combination(), #PB_Sort_Ascending | #PB_Sort_NoCase)
  
  Combination = ""
  For i = 0 To ArraySize(Combination())
    Combination + Combination(i) + "."
  Next
  Combination = LSet(Combination, Len(Combination) -1)
  
  ;La combinaison "Cube.Plane.Sphere.Cylinder" aprés tri est égale à "Cube.Cylindern.Plane.Sphere"
  
  ;3 - Création d'un pattern de travail : "Cube.Cylindern.Plane.Sphere" sera égale à A.B.C.D
  For i = 1 To CountString(Combination, Delimitator) + 1
    Pattern + Chr(64 + i) ;La lettre A commence à 65
  Next
  
  ;4 - La combinaison mémorisée est à sont tour transformée en pattern de travail
  For i = 1 To CountString(MemCombination, Delimitator) + 1
    For j = 0 To ArraySize(Combination())
      If Combination(j) = StringField(MemCombination, i, Delimitator)
        MemPattern + Chr(64 + j+1)
      EndIf
    Next
  Next
  
  ;5 - Recherche du nombre de permutation pour arriver à la combinaison "Cube.Plane.Sphere.Cylinder"
  i=1
  
  Repeat
    Permutation = SetPermutation(Pattern, i)
    
    If Permutation = MemPattern
      Debug "Il a fallu "  + i + " permutations pour arriver à la combinaison " + MemCombination
      Break
    EndIf          
    ;Permutation suivante
    i + 1
  Until Permutation = Pattern
  
  CountGroup = i
EndProcedure

;Combien de permutations il a fallut pour trouver "Cube.Plane.Sphere.Cylinder"  
GetPermutation("Cube.Plane.Sphere.Cylinder", ".")

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

Publié : lun. 29/févr./2016 22:58
par Shadow
Falsam, ton code est intéressant, merci :)

Je cherche de mon coté une solution pour que le résultat
soit un calcule rapide et donc instantané, pas simple.

Je cherche aussi à optimiser au maximum la génération des combinaisons.

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

Publié : mar. 01/mars/2016 0:13
par SPH
Spock a écrit :@SPH , il y a un truc qui déconne dans ton mélange

Code : Tout sélectionner

a$=""
For i=0 To 9
	Swap p(i),p(Random(9))
	a$+Str(p(i))
Next
Debug a$
il arrive souvent qu'il y ai plusieurs fois le meme chiffre dans la variable A$
A noter que mon code est celui ci exactement (sans bug) :

Code : Tout sélectionner

Dim p(9)

For i=0 To 9
  p(i)=i
Next

For i=0 To 9
  Swap p(i),p(Random(9))
Next

a$=""
For u=0 To 9
  a$+Str(p(u))
Next
Debug a$

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

Publié : mar. 01/mars/2016 9:19
par djes
Ce qu'il manque ici, ce sont les maths. Voici quelques liens sur les probas pour ceux qui veulent aller jusqu'au bout et nous faire de beaux programmes de loto, tiercé et autres :
http://villemin.gerard.free.fr/Wwwgvmm/ ... ctcomb.htm
http://www.alloprof.qc.ca/BV/Pages/m1346.aspx

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

Publié : mer. 02/mars/2016 20:30
par SPH
Spock a écrit :
SPH a écrit : Maintenant, ce que tu cherches est le nombre minimum d'echanges pour arriver a un arrangement precis.
Par exemple : 1,2,3,4 deviens 2,3,1,4
Et bien, le nombre d'echange est compris entre 1 et N-1
Par exemple, pour 4 elements (1,2,3,4), il faut entre 1 et 3 echanges seulement !
Exemple :
depart : 1,2,3,4
un echange : 2,1,3,4
un deuxieme echange : 2,3,1,4
fini
non !
Ne dis pas non.
J'ai raison. Voici la routine ultime qui prouve ce que j'ai dis :

Code : Tout sélectionner

Dim p(9)

For i=0 To 9
  p(i)=i
Next

For i=0 To 9
  Swap p(i),p(Random(9))
Next

pass=0

a$=""
For u=0 To 9
  a$+Str(p(u))
Next
Debug a$

Repeat
  
For i=0 To 9
  If p(i)<>i
  Swap p(i),p(p(i))
  EndIf

b$=""
ok=0
For u=0 To 9
  b$+Str(p(u))
  If p(u)=u
    ok+1
  EndIf
Next

If a$<>b$
Debug b$
pass+1
a$=b$
EndIf

If ok=10
  Goto fin
EndIf

Next

Until ok=10
fin:

Debug("Pass = "+Str(pass))
Le nombre de pass est bien de 1 a N-1 (ici de 0 a 9)

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

Publié : mer. 02/mars/2016 20:53
par SPH
Spock a écrit :
lorsqure tu me cites, ne sort pas du contexte ma citation en n'en prenant qu'une partie !

j'ai dit :
non ! car tout depends de l'algorythme utilisé !
et ça c'est une realité ! :roll:
Quel algorythme en dehorss du mien ??
Il n'y a rien a comparé puisque tu n'a rien proposé !!
Spock a écrit :j'avais aussi ecris

non ! car tout depends de l'algorythme utilisé !
car si la methode d'echange est de type :

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

il faudra 7 echanges et pas 3 ....

tout depends de l'algo de permutation employé !

bref,sans cette donnée , c'est simplement impossible de prévoir le nombre de permutation qu'il faudra pour arriver au résultat final !
et ça aussi c'est une realité !
Tu es bete ou quoi ?
Passer de :
1,2,3,4
a :
2,3,1,4
n'a jamais pris 7 pass

la preuve :
1,2,3,4
1,3,2,4
2,3,1,4

Je crois que G prouvé par un algo que l'on a besoin de 1 a N-1 pass le nombre de permutation necessaire
Toi, tu n'as rien proposé 8)

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

Publié : jeu. 03/mars/2016 1:19
par SPH
Spock a écrit :quelqu'un lui explique ? :roll:
Quoi ? Que tu n'as pas su faire le moindre morceau de code pour me surpasser ? :lol:
A moins que c'est parce que tu ne sais pas quoi dire... :mrgreen:

Perso, j'opte pour les 2 :wink: (n'est ce pas !) :idea: :idea: :idea:

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

Publié : jeu. 03/mars/2016 1:51
par SPH
1*2*3*4*...*26 = 36662860102418694144000000

Avec tout l'alphabet, je met comme prevu 25 pass maximum 8)

Code : Tout sélectionner

nb=25


Dim p(nb)

For i=0 To nb
  p(i)=i
Next

For i=0 To nb
  Swap p(i),p(Random(nb))
Next

pass=0

a$=""
For u=0 To nb
  a$+Chr(p(u)+65)
Next
Debug a$


Repeat
  
For i=0 To nb
  If p(i)<>i
  Swap p(i),p(p(i))
  EndIf

b$=""
ok=0
For u=0 To nb
  b$+Chr(p(u)+65)
  If p(u)=u
    ok+1
  EndIf
Next

If a$<>b$
Debug b$
pass+1
a$=b$
EndIf

If ok=nb+1
  Goto fin
EndIf

Next

Until ok=nb+1
fin:

Debug("Pass = "+Str(pass))
DUINMBSJCZLKOPQYVXREFTHGWA
NUIDMBSJCZLKOPQYVXREFTHGWA
NFIDMBSJCZLKOPQYVXREUTHGWA
NFCDMBSJIZLKOPQYVXREUTHGWA
NFCDOBSJIZLKMPQYVXREUTHGWA
NBCDOFSJIZLKMPQYVXREUTHGWA
NBCDOFRJIZLKMPQYVXSEUTHGWA
NBCDOFRZIJLKMPQYVXSEUTHGWA
NBCDOFRZIJKLMPQYVXSEUTHGWA
NBCDOFRZIJKLMYQPVXSEUTHGWA
NBCDOFRZIJKLMYVPQXSEUTHGWA
NBCDOFRZIJKLMYVPQGSEUTHXWA
NBCDEFRZIJKLMYVPQGSOUTHXWA
NBCDEFRZIJKLMYVPQGSTUOHXWA
NBCDEFRHIJKLMYVPQGSTUOZXWA
NBCDEFRHIJKLMYVPQGSTUOWXZA
ABCDEFRHIJKLMYVPQGSTUOWXZN
ABCDEFGHIJKLMYVPQRSTUOWXZN
ABCDEFGHIJKLMZVPQRSTUOWXYN
ABCDEFGHIJKLMZOPQRSTUVWXYN
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Pass = 20

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

Publié : jeu. 03/mars/2016 10:07
par Micoute
Très bon ça !

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

Publié : jeu. 03/mars/2016 11:35
par PAPIPP
Bonjour à tous
Je m’insinue assez rarement dans une telle discussion.
Mais j’ai l’impression qu’il y a une incompréhension entre vous.
Tout d’abord il faut distinguer le rang où l’entité observée se trouve de l’entité elle-même
Manuellement.
Pour passer d’une combinaison à une autre manuellement parmi le n ! (factorielle n)
Il suffit d’inverser 2 entités au minimum et de n déplacements maximum.
Exemple pour passer de 123 à 213 une seule inversion le 2 et le 1
Mais pour passer de 123 à 312 aucun chiffre n’est à la même place donc il faut 3 déplacements
Automatiquement.
La comme il a été dit cela dépend de l’algo mais je ne vois pas l’intérêt puisqu’on connait le résultat à obtenir.
Tout ce que l’on peut dire c’est que la gestion des mutations 2 par2 réalisée correctement permet de créer une nouvelle combinaison c’est dire qu’il faut au minimum 2*(n !) (2 fois factorielle n) sera le nombre de déplacements pour générer toutes les permutations

Petit pb parmi les n ! (factorielle n) combien y-a-t-il de permutations parmi lesquelles aucune entité ne se trouve au même rand vu du point de départ exemple à partir de 123
Il y 2 possibilités 231 et 312
Pour 1234
2143 2341 2413
4123 4321 3412
3142 4312 3421
Donc 9 possibilités

Et pour n !!!!

A+

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

Publié : jeu. 03/mars/2016 15:06
par SPH
Mon dieu, que t'es bete ! 8O

Je declare forfait 8)

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

Publié : jeu. 03/mars/2016 16:03
par Ar-S
@Dobro : SPH te dit que son algo met 23 pass à trouver le bon résultat, le tient en met (logiquement) 26

@SPH : Ok ton algo met moins de 26 pass, mais as tu vu le nombre de boucle For Next de ton code ? Du coup tes n passes d'avances sont surement moins rapides qu'un algo en 26 avec beaucoup de traitements antérieurs..

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

Publié : jeu. 03/mars/2016 16:21
par SPH
Ar-S a écrit :@Dobro : SPH te dit que son algo met 23 pass à trouver le bon résultat, le tient en met (logiquement) 26
Quel algo ? Il n'a rien pondu :idea:
Ar-S a écrit :@SPH : Ok ton algo met moins de 26 pass, mais as tu vu le nombre de boucle For Next de ton code ?
Il n'y a que 2 FOR dans ma boucle principale ! C'est ultra correcte 8)
Fuseau horaire sur UTC+01:00
Page 4 sur 4

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

Traduction française officielle © Qiaeru