Algorithme de création de suite

Question

Bonjour,

Je souhaite réaliser un algorithme permettant la création d'une suite de n caractères, pris dans 1 alphabet de 3 éléments, telle que 2 sous suites immédiatement adjacentes ne soit jamais égales.

Exemple : pour n=5 et alphabet = 1,2,3

"12312" => ok
"12323" => non ok

Je ne sais pas par où commencer, quelqu'un peut-il m'aider?

Coach42

Kotomine · Answer

je vois vraiment pas quel usage tu pourra faire de ça :d
J'ai une petite idée, pas forcément la meilleure:
Il te faut chercher pour chaque élément de ta suite, la liste des caractères interdits.

Imaginons que tu construises ta suite par ajout successif.

Pose u(n) ta String (ou suite) bien formée jusqu'au caractère n inclus.
Pose A ton alphabet ( A={1,2,3} par exemple )
Pose E(n) l'ensemble des caractères interdits pour le caractère n de ta suite (Autrement dit: A - E(n) = caractères autorisés)
E(0) = {} (trivial)

Ensuite, pour u(n+1), la va falloir analyser un peu..
Tu sais que:
u(n+1) doit différer de u(n)
, donc, Pour tout n, u(n) appartient à E(n)

Tu sais également que:
[ u(n-2) u(n-1) ]doit différer de [u(n) u(n+1)] , donc,

si u(n-2) = u(n), alors, rajouter u(n-1) a E(n)

Ainsi de suite, tu parcours l'ensemble de ta liste:

[u(n-4) u(n-3) u(n-2) ]doit différer de [ u(n-1) u(n)  u(n+1) ] : si u(n) u(n-3) ET u(n-1) u(n-4), alors, rajouter u(n-2) dans la liste

Encore un pour la route:

[u (n-6) u(n-5) u(n-4) u(n-3) ]doit differer de [   u(n-2)  u(n-1) u(n) u(n+1) ]si u(n) u(n-4) ET u(n-1) u(n-5) ET u(n-2) = u(n-6) alors, rajouter u(n-3) dans E(n+1)

Soit a une itération p vérifiant les sous suites de longueur p

[u(n-2p) ... u(n-p) ] [u(n-p+1) ... u(n+1)]

bool resultat = true

pour j de n 0 a presultat resultat AND ( u(n-j) = u(n-p-j)  )
finpour

si resultat alors E= {E u(n-p)

Et tu boucles pour p allant de n/2 a 0

Enfin,  tu fais A-E, et tu choisis un élément

;I'm just keeping the hopeless cross to increase the meaninglessness

Kotomine · Answer

Haaa, j'oubliais : ton alphabet est de longueur finie (3).
Si les sous suites de longueur 1 sont valides, ils suffit de regarder au max les 5 caractères précédents.

;I'm just keeping the hopeless cross to increase the meaninglessness

Coach42 · Answer

Merci Kotomine pour cette piste qui semble particulièrement intéressante :-)

Coach42

Algorithme de création de suite

3 réponses

Votre réponse

Discussions similaires