OVH Cloud OVH Cloud

detecter un cube abelien dans une chaine de caracteres

8 réponses
Avatar
hasni20
bonjour tt le monde,
j'ai un petit probleme en Perl, qui peut m'aider?
le voici : considerons une chaine de caractere $w, je cherche une
expression reguliere qui peut detecter si cette chaine contient un
cube abelien (avec une permutation pres des lettres), je vous donne un
exemple :
$w=aaa contient un cube
$w=abbabaca contient egalement un cube abelien abbaab
$w=cacbbaccbabba contient aussi un cube acbbaccba.
$w=ababac ne contient aucune cube.

je travaille principalement sur un alphabet a 3 lettres.
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.

je vous en remercie.
hasni.

8 réponses

Avatar
jl_morel
Dans l'article , hasni20
@caramail.com a dit...

bonjour tt le monde,
j'ai un petit probleme en Perl, qui peut m'aider?
le voici : considerons une chaine de caractere $w, je cherche une
expression reguliere qui peut detecter si cette chaine contient un
cube abelien (avec une permutation pres des lettres), je vous donne un
exemple :
$wªa contient un cube
$w«babaca contient egalement un cube abelien abbaab
$wÊcbbaccbabba contient aussi un cube acbbaccba.
$w«abac ne contient aucune cube.

je travaille principalement sur un alphabet a 3 lettres.
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.



Je propose une solution sans Regexp car je ne pense pas que ce soit l'outil
le plus commode dans ce cas.
La fonction testcube retourne le cube s'il existe, sinon une chaîne vide.

#!/usr/bin/perl -w
use strict;
use integer;

print testcube("abbaacabcaacbaacabacbdfgeraabb");

sub testcube {
my $w = shift;
for my $i (1..length($w)/3) { # $i = longueur du mot
for my $j (0..length($w)-3*$i) { # $j = offset dans $w
my $f1 = substr $w, $j, $i;
my $g1 = join '', sort split //, $f1;
my $f2 = substr $w, $j+$i, $i;
my $g2 = join '', sort split //, $f2;
next if $g1 ne $g2; # pas la peine d'aller plus loin
my $f3 = substr $w, $j+2*$i, $i;
my $g3 = join '', sort split //, $f3;
next if $g1 ne $g3;
return "$f1 $f2 $f3";
}
}
return "";
}
__END__

HTH

--
J-L.M.

Avatar
Laurent Wacrenier
hasni écrit:
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.


C'est quoi un cube abélien ?

Avatar
hasni20
Benoit Izac wrote in message news:...


J'ai bien une solution mais j'ai peur qu'elle soit un peu lente.

#!/usr/bin/perl -w
use strict;

my $w = "fgaaaejkkkilsddldabbaabjjkkdkdkabcbcaacbjdjd";

# 1 lettre
my $tmp = $w;
while ($tmp =~ /^(.)/) {
my $c = $1;
if ($tmp =~ /^$c$c$c/) {
print "il y a un cube (1): $c$c$cn";
$tmp =~ s/^..//;
}
$tmp =~ s/^.//;
}

# 2 lettres
$tmp = $w;
while ($tmp =~ /^(.)(.)/) {
my $a = $1;
my $b = $2;
if ($tmp =~ /^((?:$a$b|$b$a)(?:$a$b|$b$a)(?:$a$b|$b$a))/) {
my $cube = $1;
print "il y a un cube (2): $cuben";
$tmp =~ s/^.{5}//;
}
$tmp =~ s/^.//;
}

# 3 lettres
$tmp = $w;
while ($tmp =~ /^(.)(.)(.)/) {
my $a = $1;
my $b = $2;
my $c = $3;
if ($tmp =~ /((?:$a$b$c|$a$c$b|$b$a$c|$b$c$a|$c$a$b|$c$b$a)
(?:$a$b$c|$a$c$b|$b$a$c|$b$c$a|$c$a$b|$c$b$a)
(?:$a$b$c|$a$c$b|$b$a$c|$b$c$a|$c$a$b|$c$b$a))/x) {
my $cube = $1;
print "il y a un cube (3): $cuben";
$tmp =~ s/^.{8}//;
}
$tmp =~ s/^.//;
}
__END__


Cher Benoit,
Votre programme est pour detecter les cubes qui ne depassent pas la
longueur 3, bien que mon programme doit detecter les cube d'une
longueur quelconque.
merci.
hasni.

Avatar
hasni20
(Jean-Louis MOREL) wrote in message news:<bgjii0$q3p$...
Dans l'article , hasni20
@caramail.com a dit...

bonjour tt le monde,
j'ai un petit probleme en Perl, qui peut m'aider?
le voici : considerons une chaine de caractere $w, je cherche une
expression reguliere qui peut detecter si cette chaine contient un
cube abelien (avec une permutation pres des lettres), je vous donne un
exemple :
$wªa contient un cube
$w«babaca contient egalement un cube abelien abbaab
$wÊcbbaccbabba contient aussi un cube acbbaccba.
$w«abac ne contient aucune cube.

je travaille principalement sur un alphabet a 3 lettres.
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.



Je propose une solution sans Regexp car je ne pense pas que ce soit l'outil
le plus commode dans ce cas.
La fonction testcube retourne le cube s'il existe, sinon une chaîne vide.

#!/usr/bin/perl -w
use strict;
use integer;

print testcube("abbaacabcaacbaacabacbdfgeraabb");

sub testcube {
my $w = shift;
for my $i (1..length($w)/3) { # $i = longueur du mot
for my $j (0..length($w)-3*$i) { # $j = offset dans $w
my $f1 = substr $w, $j, $i;
my $g1 = join '', sort split //, $f1;
my $f2 = substr $w, $j+$i, $i;
my $g2 = join '', sort split //, $f2;
next if $g1 ne $g2; # pas la peine d'aller plus loin
my $f3 = substr $w, $j+2*$i, $i;
my $g3 = join '', sort split //, $f3;
next if $g1 ne $g3;
return "$f1 $f2 $f3";
}
}
return "";
}
__END__

HTH


Bonjour,
votre methode me parrait la bonne, j'ai ecrit un programme pareil mais
qui prend trop de temps a calculer, surtout que je dois trouver et
compter toutes les chaines qui evitent les cubes, juste un exemple :
on a 2480898 chaines de longueur 14 qui evitent les cubes abeliens,
donc pour retrouver les chaines de longueur 15, l'ordinateur a eu du
mal, car j'ai procede par rajouter un a,b,c a tous les mots de
longueur 14, et relancer la procedure.
je vous en remercie egalement!!
hasni.


Avatar
hasni20
Laurent Wacrenier <lwa@ teaser . fr> wrote in message news:...
hasni écrit:
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.


C'est quoi un cube abélien ?


un cube abelien est un mot de la forme XYZ tel que le mot Y contient
les memes lettres que le mot X, et pareil pour le mot Z (il contient
egalement les memes lettres que le mot X), je precise que l'ordre des
lettres est ignore.
Hasni.


Avatar
Laurent Wacrenier
hasni écrit:
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.


C'est quoi un cube abélien ?


un cube abelien est un mot de la forme XYZ tel que le mot Y contient
les memes lettres que le mot X, et pareil pour le mot Z (il contient
egalement les memes lettres que le mot X), je precise que l'ordre des
lettres est ignore.


Si l'ordre est ignoré, il est probablement impossible d'écrire ce test
sous forme d'une expression rationelle.



Avatar
Laurent Wacrenier
hasni écrit:
votre methode me parrait la bonne, j'ai ecrit un programme pareil mais
qui prend trop de temps a calculer, surtout que je dois trouver et
compter toutes les chaines qui evitent les cubes, juste un exemple :
on a 2480898 chaines de longueur 14 qui evitent les cubes abeliens,
donc pour retrouver les chaines de longueur 15, l'ordinateur a eu du
mal, car j'ai procede par rajouter un a,b,c a tous les mots de
longueur 14, et relancer la procedure.


Ce n'est pas le même problème, le méthode pour faire un test n'est pas
la même que celle pour tester toute une population.

À partir de la liste des chaînes de longueur 14 ne contenant pas de
cubes, ajouter AU DÉBUT "a", "b" ou "c" et vérifier qu'il n'y a pas de
cube AU DÉBUT, et non pas dans toute la chaîne.

Note que vous pouvez dans un bon nombre de cas vous passer de faire
les tests sur les 3 nouvelles lettres initiales, le résultat étant le
même à une permutation près. À vue de nez, il doit suffire de tester
sur la chaîne de 15 lettres quand la première est inférieure ou égale
à la seconde, etc., les autres cas se déduisent par permutation.

Avatar
Benoit Izac
Bonjour,

le 04/08/2003 à 11:25, (hasni) a écrit
dans le message :

J'ai bien une solution mais j'ai peur qu'elle soit un peu lente.
[...]



Cher Benoit,
Votre programme est pour detecter les cubes qui ne depassent pas la
longueur 3, bien que mon programme doit detecter les cube d'une
longueur quelconque.


Dans ce cas donnez-nous l'algorithme.
Si vous ne l'avez pas le bon groupe est <news:fr.comp.algorithmes>.

--
Benoit Izac