Comment est-ce que ce regex trouve les nombres triangulaires ?

Question

_{<em>Partie d'une série d'articles éducatifs sur les regex, ceci est une introduction douce au concept de références imbriquées.</em>}

Les premiers nombres triangulaires sont :

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Il existe de nombreuses façons de vérifier si un nombre est triangulaire. Il y a cette technique intéressante qui utilise des expressions régulières comme suit :

• Étant donné n, nous créons d'abord une chaîne de longueur n remplie du même caractère
• Nous faisons ensuite correspondre cette chaîne au modèle ^(\1.|^.)+$
  • n est triangulaire si et seulement si ce modèle correspond à la chaîne

Voici quelques extraits pour montrer que cela fonctionne dans plusieurs langues :

PHP (sur ideone.com)

$r = '/^(\1.|^.)+/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java (sur ideone.com)

for (int n = 0; n <= 50; n++) {
    String s = new String(new char[n]);
    if (s.matches("(\\1.|^.)+")) {
        System.out.print(n + " ");
    }
}

C# (sur ideone.com)

Regex r = new Regex(@"^(\1.|^.)+");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

Donc cette regex semble fonctionner, mais quelqu'un peut-il expliquer comment ?

Questions similaires

• Comment déterminer si un nombre est premier avec une regex ?

Answer 1

Explication

Voici une ventilation schématique du motif :

du début…
|         …à la fin
|         |
^(\1.|^.)+$
 \______/|___correspondance
  groupe 1   une ou plusieurs fois

Les (…) crochets définissent le groupe de capture 1, et ce groupe est associé plusieurs fois avec +. Ce sous-modèle est ancré avec ^ et $ pour voir s'il peut correspondre à l'ensemble de la chaîne.

Le groupe 1 essaie de correspondre aux this|that alternatives :

• \1., c'est-à-dire, ce que le groupe 1 a correspondu (auto-référence !), plus un caractère de "tout" type,
• ou ^., c'est-à-dire, juste un caractère "tout" au début

Remarquez que dans le groupe 1, nous avons une référence à ce que le groupe 1 a correspondu ! Il s'agit d'une référence imbriquée/auto, et c'est l'idée principale introduite dans cet exemple. Gardez à l'esprit que lorsqu'un groupe de capture est répété, généralement il ne conserve que la dernière capture, donc l'auto-référence dans ce cas dit essentiellement :

"Essaie de correspondre à ce que j'ai correspondu la dernière fois, plus un de plus. C'est ce à quoi je vais correspondre cette fois-ci."

Similaire à une récursion, il doit y avoir un "cas de base" avec les auto-références. Lors de la première itération du +, le groupe 1 n'avait encore rien capturé (ce qui n'est pas la même chose que de dire qu'il commence avec une chaîne vide). Par conséquent, la deuxième alternance est introduite, comme un moyen de "initialiser" le groupe 1, qui est autorisé à capturer un caractère lorsqu'il est au début de la chaîne.

Ainsi qu'il est répété avec +, le groupe 1 essaie d'abord de correspondre à 1 caractère, puis 2, puis 3, puis 4, etc. La somme de ces nombres est un nombre triangulaire.

---

Explorations supplémentaires

Remarquez que pour simplifier, nous avons utilisé des chaînes qui consistent en un même caractère répétitif comme notre entrée. Maintenant que nous savons comment fonctionne ce motif, nous pouvons voir que ce motif peut également correspondre à des chaînes comme "1121231234", "aababc", etc.

Remarquez également que si nous trouvons que n est un nombre triangulaire, c'est-à-dire n = 1 + 2 + … + k, la longueur de la chaîne capturée par le groupe 1 à la fin sera k.

Ces deux points sont illustrés dans l'extrait C# suivant (également visible sur ideone.com) :

Regex r = new Regex(@"^(\1.|^.)+$");

Console.WriteLine(r.IsMatch("aababc"));     // True
Console.WriteLine(r.IsMatch("1121231234")); // True
Console.WriteLine(r.IsMatch("iLoveRegEx")); // False

for (int n = 0; n <= 50; n++) {
    Match m = r.Match("".PadLeft(n));
    if (m.Success) {
       Console.WriteLine("{0} = sum(1..{1})", n, m.Groups[1].Length);
    }
}
// 1 = sum(1..1)
// 3 = sum(1..2)
// 6 = sum(1..3)
// 10 = sum(1..4)
// 15 = sum(1..5)
// 21 = sum(1..6)
// 28 = sum(1..7)
// 36 = sum(1..8)
// 45 = sum(1..9)

---

Notes sur les variantes

Toutes les variantes ne prennent pas en charge les références imbriquées. Familiarisez-vous toujours avec les particularités de la variante avec laquelle vous travaillez (et par conséquent, il est presque toujours utile de fournir ces informations lorsque vous posez des questions liées aux expressions rationnelles).

Dans la plupart des variantes, le mécanisme standard de correspondance des expressions rationnelles essaie de voir si un motif peut correspondre à n'importe quelle partie de la chaîne d'entrée (éventuellement, mais pas nécessairement, l'ensemble de l'entrée). Cela signifie que vous devez toujours ancrer votre motif avec ^ et $ lorsque c'est nécessaire.

Java est légèrement différent en ce sens que String.matches, Pattern.matches et Matcher.matches tentent de faire correspondre un motif à l'ensemble de la chaîne d'entrée. C'est pourquoi les ancres peuvent être omises dans l'extrait ci-dessus.

Notez que dans d'autres contextes, vous devrez peut-être utiliser les ancres \A et \Z à la place. Par exemple, en mode multiline, ^ et $ correspondent au début et à la fin de chaque ligne de l'entrée.

Une dernière chose est qu'avec les regex .NET, vous POUVEZ en fait obtenir toutes les captures intermédiaires réalisées par un groupe de capture répété. Dans la plupart des variantes, ce n'est pas possible : toutes les captures intermédiaires sont perdues et vous ne conservez que la dernière.

Questions connexes

• (Java) method matches not work well - avec des exemples sur la façon de faire des correspondances de préfixe/suffixe/infixe
• Is there a regex flavor that allows me to count the number of repetitions matched by * and + (.NET !)

---

Matériel bonus : Utiliser les regex pour trouver les puissances de deux !!!

Avec une très légère modification, vous pouvez utiliser les mêmes techniques présentées ici pour trouver les puissances de deux.

Voici la propriété mathématique de base que vous souhaitez exploiter :

• 1 = 1
• 2 = (1) + 1
• 4 = (1+2) + 1
• 8 = (1+2+4) + 1
• 16 = (1+2+4+8) + 1
• 32 = (1+2+4+8+16) + 1

La solution est donnée ci-dessous (mais essayez de la résoudre vous-même en premier !!!!)

(voir sur ideone.com en PHP, Java et C#) : ^(\1\1|^.)+.$