Discussion :

[maryooman]

Bonjour,

J'ai déjà écris un message dans le forum PHP mais je me suis rendu compte que c'est plus un problème d'algo.

Je possède un tableau, avec des sous tableaux, de la forme :

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
 
array(3) {
 array(2) {
  [0] => string(5) "15110"
  [0] => string(5) "59999"
 }
 array(1) {
  [0] => string(2) "it"
 }
 array(1) {
  [0] => string(5) "fr"
  [0] => string(5) "uk"*
  [0] => string(5) "spane"
 }
}

L’idée est de concorder chaque terme pour faire :

‘15110 it fr’
‘15110 it uk’
‘15110 it spane’
‘59999 it fr’
‘59999 it uk’
‘59999 it spane’

Sachant que le nombre de sous tableau est aléatoire.

Comment réaliser les chaines de caractère ci-dessus, sachant que je le nombre de tableau est variable ?
Merci.

[Invité]

Bonjour,

Je crois que ce que tu veux faire s'appelle le produit cartésien infini. C'est toujours bon à savoir.

Est-ce que c'est envisageable pour toi d'utiliser des listes chaînées ? Si c'est oui, j'ai une vague idée de comment faire. Sinon je vois pas comment faire sans faire de nombreuses réallocations mémoires.

Voici un exemple de liste chainée en php.

[maryooman]

Je peux utiliser une liste chaînées.
Mais je n'ai pas d'algo qui me viens à l'esprit.

[Invité]

Tu peux décomposer ton problème en deux sous-problèmes plus simples.

D'abord tu doit d'abord être capable de faire le produit cartésien entre deux tableaux de chaines de caractères.

Par exemple, tu doit faire une fonction qui transforme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
array(3) {
 array(2) {
  [0] => string(5) "15110"
  [1] => string(5) "59999"
 }
 array(3) {
  [0] => string(2) "fr"
  [1] => string(2) "uk"
  [2] => string(5) "spane"
 }
}

en ça :

Code :

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

1
2
3
4
5
6
7
8
array(6) {
  [0] => string(8) "15110 fr"
  [1] => string(8) "15110 uk"
  [2] => string(11) "15110 spane"
  [3] => string(8) "59999 fr"
  [4] => string(8) "59999 uk"
  [5] => string(11) "59999 spane"
}

On va appeler cette fonction "produit_cartesien_2".

Une fois que t'as cette fonction, tu l'applique sur les deux premiers tableaux de chaines de caractères. Tu obtiens un tableau de chaines nommé T12 que tu garde en mémoire.

Ensuite tu appliques la fonction "produit_cartesien_2" sur le tableau T12 et sur le 3ème tableau. Tu obtiens le tableau T123 que tu garde en mémoire (tu peux jeter T12 maintenant).

Ensuite tu applique la fonction "produit_cartésien_2" sur le tableau T123 et sur le 4ème tableau ...

--------------------------------------------------------------------
--------------------------------------------------------------------

Tout ça, tu peux le faire avec des tableaux classiques, mais c'est plus efficace en utilisant des listes chainées pour la construction progressive de T12, T123, T1234, ...

Par exemple pour concaténer deux tableaux de caractères "abc" et "def", tu doit créer un 3ème tableau de 6 caractères, recopier le 1er tableau, puis recopier le 2ème tableau, puis détruire les deux premiers tableaux.

Dans cet algorithme, si on utilise des tableaux, on va faire cela de très nombreuses fois :

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
"abc" + "def" + "ghi" + jkl"
 
-> allocation d'un tableau de 6 caractères
-> destruction de deux tableaux de 3 caractères
 
"abcdef" + "ghi" + "jkl"
 
-> allocation d'un tableau de 9 caractères
-> destruction d'un tableau de 6 caractères et un autre de 3
 
"abcdefghi" + "jkl"
 
-> allocation d'un tableau de 12 caractères
-> destruction d'un tableau de 9 caractères et un autre de 3
 
"abcdefghijkl"

Alors que si on utilise des listes chainées, on a juste à les coller bout à bout (une seule affectation est nécessaire) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
"abc" + "def" + "ghi" + jkl"
 
-> affectation du pointeur de la lettre c vers la lettre d
 
"abcdef" + "ghi" + "jkl"
 
-> affectation du pointeur de la lettre f vers la lettre g
 
"abcdefghi" + "jkl"
 
-> affectation du pointeur de la lettre i vers la lettre j
 
"abcdefghijkl"

[maryooman]

mais c'est une idée excellent hellfoust !!

je me lance dans le code tout de suite.

Merci !

[pseudocode]

Sinon un simple appel récursif permet de concaténer dynamiquement les éléments de chaque tableau. Je pense qu'en cherchant "produit cartésien" sur ce forum tu trouveras des explications.