Discussion :

[djibril]

Salut,

Je cherche un petit algorithme pour résoudre ma problématique.

A partir de la liste suivante : 1, 1, 2, 2, 1, 2, 3, 2, 1, 1 je souhaiterais obtenir ceci : 1, 2, 2.1, 2.2, 3, 3.1, 3.1.1, 3.2, 4, 5.
En faite, dans la première liste, j'ai une suite de chiffres correspond à un niveau de titre d'un document, un sommaire. Exemple :
1- mon titre (niveau 1)
2- mon titre (niveau 1)

2.1- sous-titre (niveau 2)
2.2- sous-titre (niveau 2)

3- mon titre (niveau 1)

3.1- sous-titre (niveau 2)

3.1.1- sous-titre (niveau 3)

3.2- sous-titre (niveau 2)

4- mon titre (niveau 1)
5- mon titre (niveau 1)

Merci pour les courageux se penchant sur mon souci.

[mamax29]

Si on se limite à une profondeur de "3", voici ce que je te propose:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
41
42
43
44
45
46
#!C:\strawberry\perl\bin
 
use warnings;
use strict;
my @input = (1, 1, 2, 2, 1, 2, 3, 2, 1, 1);
my @output;
 
my $nb_niveau_1 = 0;
my $nb_niveau_2 = 0;
my $nb_niveau_3 = 0;
 
for (my $i = 0; $i<scalar(@input); $i++)
{
	print $input[$i]." - ";
}
 
print "\n";
 
for (my $i = 0; $i<scalar(@input); $i++)
{
	if ($input[$i] == 1)
	{
		$nb_niveau_1++;
		$nb_niveau_2 = 0;
		$nb_niveau_3 = 0;
		$output[$i] = $nb_niveau_1;
	}
	if ($input[$i] == 2)
	{
		$nb_niveau_2++;
		$nb_niveau_3 = 0;
		$output[$i] = $nb_niveau_1.".".$nb_niveau_2;
	}
	if ($input[$i] == 3)
	{
		$nb_niveau_3++;
		$output[$i] = $nb_niveau_1.".".$nb_niveau_2.".".$nb_niveau_3;
	}
}
 
 
for (my $i = 0; $i<scalar(@output); $i++)
{
	print $output[$i]." - ";
}
print "\n";

[djibril]

Merci pour ta proposition mais la profondeur peut aller jusqu'à 10. Au delà de 10, ça m'étonnerait.

[Philou67430]

Merci pour ce petit défi d'algorithmique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/perl
 
use strict;
use warnings;
 
my @level = qw(1 1 2 2 1 2 3 2 1 1);
 
my @stack = (0);
foreach my $level (@level) {
  push @stack, "0" if $level > @stack;
  pop @stack       if $level < @stack;
  $stack[-1]++;
  print "".(join ".", @stack)."\n";
}

[djibril]

Merci pour ce petit défi d'algorithmique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/perl
 
use strict;
use warnings;
 
my @level = qw(1 1 2 2 1 2 3 2 1 1);
 
my @stack = (0);
foreach my $level (@level) {
  push @stack, "0" if $level > @stack;
  pop @stack       if $level < @stack;
  $stack[-1]++;
  print "".(join ".", @stack)."\n";
}

[djibril]

euh, il y a un souci dans ton algo Philou.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

my @level = qw(1 1 2 2 1 2 3 2 1 1 1 2 3 1);

Ne donne pas le bon résultat :

1
2
2.1
2.2
3
3.1
3.1.1
3.2
4
5
6
6.1
6.1.1
6.2

au lieu de

1
2
2.1
2.2
3
3.1
3.1.1
3.2
4
5
6
6.1
6.1.1
7

[Philou67430]

Possible, je ne l'ai testé qu'avec ton jeu d'essai...

Exact, il faut compter l'écart de niveau, surtout en remontant.
Je corrige...

[djibril]

Possible, je ne l'ai testé qu'avec ton jeu d'essai...

voir jeu ci-dessus

[djibril]

La logique veut que l'on puisse passer d'un sous-titre de niveau inférieur au plus haut possible, par exemple du niveau 3 au 1.
Dans le sens inverse, ce n'est biensûr pas possible.
On peut avoir un sommaire de ce type :
1 Titre niveau 1
2 Titre niveau 1
2.1 titre niveau 2
2.1.1 titre niveau 3
3 titre niveau 1
Ce qui correspond au jeu 1 1 2 3 1

[Philou67430]

La correction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/perl
 
use strict;
use warnings;
 
my @level = qw(1 1 2 2 1 2 3 2 1 1 1 2 3 1);
 
my @stack = (0);
foreach my $level (@level) {
  push @stack, 0 while ($level > @stack);
  pop @stack     while ($level < @stack);
  $stack[-1]++;
  print "".(join ".", @stack)."\n";
}

Avec cet algo, tu peux montrer ou descendre d'autant de niveau que tu veux (sans dépasser le niveau 0 en remontant bien sur)

[djibril]

La correction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/perl
 
use strict;
use warnings;
 
my @level = qw(1 1 2 2 1 2 3 2 1 1 1 2 3 1);
 
my @stack = (0);
foreach my $level (@level) {
  push @stack, 0 while ($level > @stack);
  pop @stack     while ($level < @stack);
  $stack[-1]++;
  print "".(join ".", @stack)."\n";
}

Eh beh, je dis chapeau !!

[Philou67430]

En tout cas, j'adore. Si tu as d'autres problèmes d'algorithmie, n'hésite pas... détente assurée.

[djibril]

Merci également à mamax29 !

[mamax29]

oui, mais j'ai rien compris à l'algo de Philou67430

[Philou67430]

J'utilise une pile qui sauve l'indice courant de chaque niveau.
Si le niveau change par rapport au dernier niveau de la pile (en gros, que la taille de ma pile est différente du niveau vers lequel on veut aller), je fais évoluer ma pile :
- en ajoutant autant d'élément que nécessaire si le niveau monte
- en retirant autant d'élément que nécessaire si le niveau baisse
Pour afficher le numéro de paragraphe, il suffit de concaténer tous les niveaux de la pile en les séparant d'un "."

[Dimitry.e]

Puisque je suis dans ma période "moins j'en écris mieux c'est" (et que je m'ennuie) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
my @t = qw(1 1 2 2 1 2 3 2 1 1 1 2 3 1);
my @s;
foreach ( @t ) {
  @s = ( @s[0..$_ - 2 ], ++$s[$_ - 1] );
  print join( '.', @s ), "\n";  
}

[lilian_h]

Hello !

Même en Shell c'est drôle !

Mais moi je suis parti sur une fonction récursive.

Djibril, tu souhaites générer de la doc ?

Lilian.

[djibril]

Oui, je suis en train de bosser sur de la conversion de fichiers XML en fichier OpenOffice et l'inverse.

[Philou67430]

Excellente solution qui joue sur le fait que @s[0..-1] ne retourne ni erreur, ni warning, mais une liste vide.

[lilian_h]

Ok,

Si ça t’intéresses, j'ai écris un script Perl permettant de générer des fichiers docx à partir d'un template docx et de fichiers de variables.
Peut-être que le format OOXML n'est pas si éloigné que cela des fichiers OpenOffice.

Lilian.