déterminer si un tableau est périodique ?

Salut,

je cherche un algorithme pour déterminer est ce qu'un tableau est périodique "cyclique" ou non?

pour simplifier mon tableau est de type enum qui prend comme valeur: -1 ou 1.
exemple: [1,-1,1, 1,-1,1, 1,-1,1 ....1,-1,1] est un tableau périodique dont le cycle est [1.-1.1].

Merci d'avance :)

salut,
déja pour avancer on retiendra qu'un tableau cyclique a des cycles pairs si sa longueur est paire et des cycles impaires dans le cas contraire.
donc je pars du premier élement du tableau tab[1] en supposant que l'on a un tableau allant de 1 a N (n elements).
N paire.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

je parcours le tableau jusqu'à N/2 a la recherche de tab[1]. { [I]for i=1;i=n/2;i++ if tab==tab[1] { premier element tab[1] trouvé je teste si i est pair, if(i % 2)==0 { je peux tester si tab[1,i] est cyclique ... j'extrait le tableau tab[i+1,2i+1] si c n'est pas la meme sequence alors ce tableau n'est pas cyclique } else i n'est pas pair il est impair alors i+1 est pair { CHOIX 1 : tab[i+1]==tab[1] dans ce cas on peut faire le test de cyclique CHOIX 2 : tab[i+1]!=tab[1] alors soit ce tableau n'est pas cyclique , soit ce tableau est cyclique depuis (i+1)/2 } } }

---

je vous laisse la suite ....

Citation:

---

déja pour avancer on retiendra qu'un tableau cyclique a des cycles pairs si sa longueur est paire et des cycles impaires dans le cas contraire.

---

Et pourquoi ne pas généraliser?
Commencer par lister les diviseurs de n où n est la longueur du tableau.
La longueur d'un cycle période doit être un de ces diviseurs.

bien Zavonen, ce que tu as dit c'est cool.c'est toujours un diviseur.je pense que cela peut aider dans la recherche de la solution.On va s'y pencher:D

Je vais peut-être dire une grosse bêtise, mais ne suffit-il pas de verifier que tab[i] == tab[ (i % seqlen) ], et si ce n'est pas le cas d'augmenter la taille de seqlen en conséquence ?

Code:

---

1 2 3 4 5 6 7 8 9

double[] tab = {1,-1.1, 1,-1.1, 1,-1.1};   int seqlen=1; for(int i=0;i<tab.length;i++) if (tab[i] != tab[i%seqlen]) seqlen=(i+1);   if ((seqlen<tab.length) && (tab.length%seqlen)==0) System.out.println("periodic sequence of length = "+seqlen);

---

Non pseudocode, tu ne dis pas une bêtise, mais disons que si la longueur len du tableau est 125, ce n'est pas la peine d'essayer avec seqlen =2,3,4,6, ce que feras avec ton algo puisque tu commences à 1 et tu incrémentes d'une unité à chaque tour de boucle.
Donc il faut, à mon sens, commencer par isoler la liste des diviseurs de n (longueur totale du tableau).
Après on peut faire comme toi avec seqlen parcourant cette liste, ou alors rendre tab[0:seqlen] le comparer globalement avec tab[seqlen,2*seqlen], etc...
A priori je ne sais pas si une des deux méthodes est dans l'absolu (en moyenne) meilleure que l'autre. On peut facilement trouver des exemples où ta méthode est meilleure et d'autres où c'est le contraire.
Il y a quand même quelque chose qui me dérange dans ton code.
Une fois que tu as décelé que tab[i] != tab[i%seqlen] tu en conclus qu'il ne peut y avoir de cycle de longueur seqlen, tu passes donc au suivant, mais dans ce cas il faut recommencer ta boucle i avec i=0.
J'aurais donc vu plutôt deux boucles imbriquées.
Une boucle i à l'intérieur d'une boucle seqlen.

Citation:

---

Envoyé par Zavonen

Il y a quand même quelque chose qui me dérange dans ton code.
Une fois que tu as décelé que tab[i] != tab[i%seqlen] tu en conclus qu'il ne peut y avoir de cycle de longueur seqlen, tu passes donc au suivant, mais dans ce cas il faut recommencer ta boucle i avec i=0.
J'aurais donc vu plutôt deux boucles imbriquées.
Une boucle i à l'intérieur d'une boucle seqlen.

---

Mon idée c'est de dire que tant que la séquence actuelle fonctionne, on continue l'exploration de la chaine avec cette séquence.

Dés que ca ne fonctionne plus, on considère que tous les caractères qu'on a lu depuis le début n'étaient pas répétés mais formaient la base de la "véritable" séquence. Cette véritable séquence va donc du 1er caractère jusqu'a l'actuel. Et si on a vu juste, le caractère suivant sera égal au premier.

Mais bon, ce que je dis est peut être faux. :aie:

Citation:

---

Envoyé par pseudocode

Mon idée c'est de dire que tant que la séquence actuelle fonctionne, on continue l'exploration de la chaine avec cette séquence.

Dés que ca ne fonctionne plus, on considère que tous les caractères qu'on a lu depuis le début n'étaient pas répétés mais formaient la base de la "véritable" séquence. Cette véritable séquence va donc du 1er caractère jusqu'a l'actuel. Et si on a vu juste, le caractère suivant sera égal au premier.

Mais bon, ce que je dis est peut être faux. :aie:

---

…en tous cas l'implémentation ne fait pas ce que vous pensez…

question :

pour [ 1,-1, 1,-1, 1,-1, 1,-1 ]
2 ou 4 ?

le plus petit cycle ou le plus grand ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#!/usr/bin/env ruby   tabs = [ [ 1,-1,1, 1,-1,1, 1,-1,1, 1,-1,1 ], [ 1,-1, 1,-1, 1,-1, 1,-1 ], [ 1,-1, 1,-1, 1,-1, 1,-1, 1, -1 ], [ 1,-1,-2, 1,-1,-2, 1,-1,-3 ], [ 1,-1,1,2, 1,-1,1,2 ] ]   tabs.each do |tab| tab.each do |t| print "#{t}, " end puts   seqlen=1 i= 0   while i+seqlen < tab.length if tab[i] != tab[(i + seqlen)] seqlen=seqlen+1 i = 0 end i+=1 end   if ((seqlen<tab.length) && (tab.length%seqlen)==0) puts "periodic sub-sequence of length = #{seqlen}" else puts "no sub-sequence" end puts end

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, periodic sub-sequence of length = 3   1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2   1, -1, 1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2   1, -1, -2, 1, -1, -2, 1, -1, -3, no sub-sequence   1, -1, 1, 2, 1, -1, 1, 2, periodic sub-sequence of length = 4

---

Citation:

---

Envoyé par JeitEmgie

…en tous cas l'implémentation ne fait pas ce que vous pensez…

---

Ah ?

Citation:

---

pour [ 1,-1, 1,-1, 1,-1, 1,-1 ]
2 ou 4 ?

le plus petit cycle ou le plus grand ?

---

Tant que le cycle de longueur 2 fonctionne, on le conserve. Donc le plus petit cycle.

Citation:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, periodic sub-sequence of length = 3   1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2   1, -1, 1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2   1, -1, -2, 1, -1, -2, 1, -1, -3, no sub-sequence   1, -1, 1, 2, 1, -1, 1, 2, periodic sub-sequence of length = 4

---

---

Bah ca m'a l'air bon, non ?

Citation:

---

Envoyé par pseudocode

Ah ?



Tant que le cycle de longueur 2 fonctionne, on le conserve. Donc le plus petit cycle.



Bah ca m'a l'air bon, non ?

---

oui mais c'est votre code avec mes modifications… ;)

diff principale étant :

Code:

---

1 2 3 4 5

if tab[i] != tab[(i + seqlen)] seqlen=seqlen+1 i = 0 end

---

vous utilisiez i % seqlen et ne remettiez pas i à 0…
le test du while est aussi différent…

NB
une simple modification trouve toutes les séquences :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#!/usr/bin/env ruby   tabs = [ [ 1,-1,1, 1,-1,1, 1,-1,1, 1,-1,1 ], [ 1,-1, 1,-1, 1,-1, 1,-1 ], [ 1,-1, 1,-1, 1,-1, 1,-1, 1, -1 ], [ 1,-1,-2, 1,-1,-2, 1,-1,-3 ], [ 1,-1,1,2, 1,-1,1,2 ] ]   tabs.each do |tab| tab.each do |t| print "#{t}, " end puts   seqlen=1 i=0   while seqlen<tab.length while i+seqlen < tab.length if tab[i] != tab[(i + seqlen)] seqlen=seqlen+1 i = 0 end i+=1 end   if ((seqlen<tab.length) && (tab.length%seqlen)==0) puts "periodic sub-sequence of length = #{seqlen}" seqlen=seqlen+1 i=0 else puts "no (more) sub-sequence" seqlen=tab.length end end puts end

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, periodic sub-sequence of length = 3 periodic sub-sequence of length = 6 no (more) sub-sequence   1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2 periodic sub-sequence of length = 4 no (more) sub-sequence   1, -1, 1, -1, 1, -1, 1, -1, 1, -1, periodic sub-sequence of length = 2 no (more) sub-sequence   1, -1, -2, 1, -1, -2, 1, -1, -3, no (more) sub-sequence   1, -1, 1, 2, 1, -1, 1, 2, periodic sub-sequence of length = 4 no (more) sub-sequence

---

Citation:

---

vous utilisiez i % seqlen et ne remettiez pas i à 0…

---

C'est ce que j'avais signalé.

Ceci fait l'affaire

Code:

---

1 2 3 4 5 6 7

Tab=[1,0,1,1,0,1,1,0,1] n= len(Tab) D=[k for k in range(1,n+1) if n%k==0] for k in D: if Tab==Tab[0:k]*(n/k): print Tab[0:k] break

---

Citation:

---

Envoyé par JeitEmgie

oui mais c'est votre code avec mes modifications… ;)

diff principale étant :

Code:

---

1 2 3 4 5

if tab[i] != tab[(i + seqlen)] seqlen=seqlen+1 i = 0 end

---

vous utilisiez i % seqlen et ne remettiez pas i à 0…
le test du while est aussi différent…

---

Arf. Oui effectivement, la prochaine séquence valide ne commence pas forcément a "i+1", en cas de doublon du 1er caractère. Il faut alors faire un backtrack a la position du 1er doublon.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

int mark=-1, seqlen=1; for(int i=1;i<tab.length;i++) {   // possible start of new subseq if (mark==-1 && tab[i]==tab[0]) mark=i;   if (tab[i]!=tab[i%seqlen]) { // try next subseq if (mark!=-1) {i=mark; mark=-1;} seqlen=i+1; } }     if ((seqlen<tab.length) && (tab.length%seqlen)==0) System.out.println("periodic sub-sequence of length = "+seqlen);

---

Sinon tu fais une FFT sur ta serie :aie:.

Citation:

---

Envoyé par Zavonen

Ceci fait l'affaire

Code:

---

1 2 3 4 5 6 7

Tab=[1,0,1,1,0,1,1,0,1] n= len(Tab) D=[k for k in range(1,n+1) if n%k==0] for k in D: if Tab==Tab[0:k]*(n/k): print Tab[0:k] break

---

---

pouvez vous m'expliquer le code? ça a l'air très proche de OPL avec le quel je vais implémenter l'algo.

Merci :)

Citation:

---

Envoyé par SmileSoft

pouvez vous m'expliquer le code? ça a l'air très proche de OPL avec le quel je vais implémenter l'algo.

Merci :)

---

La concision de Python est très alléchante…
mais méfiez-vous quand même concision du code source n'est toujours équivalent à rapidité…

sur la même machine, le code Python donne :

Code:

---

1 2 3 4

real 0m0.309s user 0m0.011s sys 0m0.017s

---

contre en Ruby :

Code:

---

1 2 3 4

real 0m0.044s user 0m0.004s sys 0m0.004s

---

pour l'algorithme de pseudocode que j'ai corrigé pour sortir toutes les sous-séquences… et pas seulement la plus courte…

et quand il ne sort que la plus courte :

Code:

---

1 2 3 4

real 0m0.006s user 0m0.003s sys 0m0.003s

---

çà vaut la peine de comparer sous différents environnements… pour lisser l'effet "plate-forme"…

Citation:

---

Envoyé par JeitEmgie

La concision de Python est très alléchante…
mais méfiez-vous quand même concision du code source n'est toujours équivalent à rapidité…
(...)
çà vaut la peine de comparer sous différents environnements… pour lisser l'effet "plate-forme"…

---

Oui mais là c'est surtout l'efficacité de l'implémentation qu'on mesure, et pas celle de l'algo.

L'algo de zavo est celui qui exécute le minimum d'opérations (grace a son précalcul des diviseurs) mais ce sont des opérations qui sont très "couteuse" (par exemple le Tab==Tab[0:k]*(n/k) qui doit construire une copie tableau puis le comparer).

L'idée de zavo reste a mon sens la meilleure. On peut par contre optimiser son implémentation en evitant la construction de tableaux, ou le précalcul de tous les diviseurs.

Citation:

---

Envoyé par pseudocode

Oui mais là c'est surtout l'efficacité de l'implémentation qu'on mesure, et pas celle de l'algo.

L'algo de zavo est celui qui exécute le minimum d'opérations (grace a son précalcul des diviseurs) mais ce sont des opérations qui sont très "couteuse" (par exemple le Tab==Tab[0:k]*(n/k) qui doit construire une copie tableau puis le comparer).

L'idée de zavo reste a mon sens la meilleure. On peut par contre optimiser son implémentation en evitant la construction de tableaux, ou le précalcul de tous les diviseurs.

---

certes…
mais quand on compare le nombre d'opérations il faut que celles-ci soient du même niveau de complexité…
et comme vous le dites les opérations de la version Python sont très coûteuses…
donc il y a aura une pénalité qui ne sera compensée qu'à partir d'une certaine taille de tableau…
(du moins si le coût caché n'est pas dû à des allocations de mémoire temporaire dans l'évaluation de certaines expressions de tableaux par Python… auquel cas même si l'algorithme est plus élégant, son implémentation en Python restera pénalisante…)

Citation:

---

Envoyé par JeitEmgie

certes…
mais quand on compare le nombre d'opérations il faut que celles-ci soient du même niveau de complexité…
et comme vous le dites les opérations de la version Python sont très coûteuses…
donc il y a aura une pénalité qui ne sera compensée qu'à partir d'une certaine taille de tableau…
(du moins si le coût caché n'est pas dû à des allocations de mémoire temporaire dans l'évaluation de certaines expressions de tableaux par Python… auquel cas même si l'algorithme est plus élégant, son implémentation en Python restera pénalisante…)

---

mais moi je vais l'implémenter dans OPL "Optimization Programming Language" dont la périodicité d'une séquence donnée sera implémentée comme Contrainte, qui connait OPL pour en déduire la complexité? :aie:
restons dans l'algo, quelqu'un pour m'expliquer le code de Zavonen ? :roll:

Merci :)

Citation:

---

Envoyé par SmileSoft

restons dans l'algo, quelqu'un pour m'expliquer le code de Zavonen ? :roll:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

# La séquence a étudier Tab=[1,0,1,1,0,1,1,0,1]   # La longueur de la séquence a étudier n= len(Tab)   # La liste des diviseurs de "n" D=[k for k in range(1,n+1) if n%k==0]   # Pour chaque diviseur "k" contenu dans la liste D for k in D:   # si le tableau est une répétition des "k" premiers éléments if Tab==Tab[0:k]*(n/k): # afficher les "k" premiers éléments print Tab[0:k] # et quitter la boucle break

---