Discussion :

[guyomel]

Bonjour,

Voici mon problème, j'ai trois possibilité et un temps T, je doit énumérer les possibilité. Par exemple:

Possibilité={a,b,c} et T= 2

énumération={aa,ab,ac,ba,bb,bc, ca,cb,cc}

Aussi, j'ai pensé réaliser un arbre ternaire complet de profondeur T. Quelque chose du genre, pour T=1

racine
/ | \
a b c

Cependant, je ne vois pas comment réaliser l'algorithme...
Merci d'avance

PS: je code en Java

[Alp]

Il s'agit pas tellement d'un arbre.

Pour la profondeur, c'est bien T.

Ensuite, tu pars de 3 noeuds a, b, c.
A chacun tu donnes comme fils de nouveau a, b, c. Et tu répètes cela jusqu'à atteindre la profondeur T. Ca te donne :
a - a
a - b
a - c
b - a
b - b
b - c
c - a
c - b
c - c

Et ensuite, tu fais un parcours de profondeur T exactement pour obtenir un chemin, et tu répètes jusqu'à avoir parcouru tous les chemins possibles.

[guyomel]

Merci, je vois bien l'idée mais je ne vois pas comment le coder...
mon idée de base était très classique:

class node {
node a,b,c
node father
}

class tree {
node root
int T
}

mais pour le

A chacun tu donnes comme fils de nouveau a, b, c. Et tu répètes cela jusqu'à atteindre la profondeur T

. Je vois pas trop comment faire. Ce ne serai qu'à la profondeur 2, j'ai 3 pères et je vois mal par comment passer de l'un a l'autre pour créer les 9 feuilles...

[Alp]

C'est pour ça que ça n'est pas un arbre. Il y a 3 racines : a,b,c.

[pseudocode]

mais pour le . Je vois pas trop comment faire. Ce ne serai qu'à la profondeur 2, j'ai 3 pères et je vois mal par comment passer de l'un a l'autre pour créer les 9 feuilles...

Par recursion (ou par une pile).

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
 
class Node {
	Node a,b,c;
	Node father;
	Node(Node father) {this.father=father;}
}
 
class Tree {
	Node root;
	int T;
}

Code java :

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
 
private void populate(Node n, int maxt, int t) {
	n.a = new Node(n);
	n.b = new Node(n);
	n.c = new Node(n);
	if (t>=maxt) return;
	populate(n.a,maxt,t+1);
	populate(n.b,maxt,t+1);
	populate(n.c,maxt,t+1);
}
 
public Tree buildTree(int T) {
	Tree tree = new Tree();
	tree.root = new Node(null);
	tree.T = T;
 
	populate(tree.root, tree.T, 1);
 
	return tree;
}