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

[falsam]

Moi aussi je l'ai dit

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

[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", ".")

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

[SPH]

@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$

[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

[SPH]

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)

[SPH]

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

Quel algorythme en dehorss du mien ??
Il n'y a rien a comparé puisque tu n'a rien proposé !!

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é

[SPH]

quelqu'un lui explique ?

Quoi ? Que tu n'as pas su faire le moindre morceau de code pour me surpasser ?
A moins que c'est parce que tu ne sais pas quoi dire...

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

[SPH]

1*2*3*4*...*26 = 36662860102418694144000000

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

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

[Micoute]

Très bon ça !

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

[SPH]

Mon dieu, que t'es bete !

Je declare forfait

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

[SPH]

@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

@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