Accès Premium
GNT sans publicité, site mobile, fonctionnalitées exclusives...
Rejoignez-nous !
Forums Développement Langage Perl

detecter un cube abelien dans une chaine de caracteres

Le
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ª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 vous en remercie.
hasni.
Lire les 8 réponses

Questions / Réponses high-tech
Poser une question
Vidéos High-Tech et Jeu Vidéo
Plus de vidéos
Téléchargements
Plus de téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
jl_morel
Le #150218
Dans l'article @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.

Répondre en citant
Laurent Wacrenier
Le #150217
hasni
Qui pourrait m'ecrire une expressions reguliere testant si $w contient
un cube abelien ou non.


C'est quoi un cube abélien ?

Répondre en citant
hasni20
Le #150216
Benoit Izac

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.

Répondre en citant
hasni20
Le #150215
(Jean-Louis MOREL) wrote in message news:
Dans l'article @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.


Répondre en citant
hasni20
Le #150214
Laurent Wacrenier
hasni
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.


Répondre en citant
Publicité
Suivre les réponses
Poster une réponse
Anonyme