Déterminer des fréquences de chaque chaines->une liste de liste

Habmra -  
 Habmra -
Bonjour,
J'ai besoin d'une piste(algo) pour calculer les fréquences dans une liste de liste, la forme de ma liste est comme suite:

[Mini liste [it=[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64]] , Mini liste [it=[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64]] , Mini liste [it=[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64]] , Mini liste [it=[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64]],Mini liste [it=[11, 59, 3] , Mini liste [it=[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64], Mini liste [it=[11, 59, 3]]

Une liste dont chaque élément contient une liste par exemple:
[11, 13, 48, 27, 15, 97, 7, 62, 8, 34, 64]

ce que je veux faire , c'est que je doit compter pour chaque chaine par exemple "11" le nombre de fois qu'il est en premier et ensuit le nombre de fois qu'il y 11 13 ou 11 59 ainsi de suite.
Après le calcule je dois stocker les éléments plus leurs nombre d'apparition.
j'ai arrivé d'avoir comme résultat :
[Node [it=11, freq=20], Node [it=11/13, freq=16], Node [it=11/13/48, freq=16], Node [it=11/13/48/27, freq=16], Node [it=11/13/48/27/15, freq=16], Node [it=11/13/48/27/15/97, freq=16], Node [it=11/13/48/27/15/97/7, freq=16], Node [it=11/13/48/27/15/97/7/62, freq=16], Node [it=11/13/48/27/15/97/7/62/8, freq=16], Node [it=11/13/48/27/15/97/7/62/8/34, freq=31]]

mais mon algo zappe quelques éléments

SVP aidez moi dans ce sens et merci pour votre temps
Cordialement
A voir également:

2 réponses

Réponse 1 / 2
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Bonsoir,

Je ne suis pas sûr d'avoir bien compris le problème.

Tu as une 
List<List<E>> a
et tu veux obtenir une 
List<Node<List<E>,Integer>> b
telle que pour 
Node(list,n)
dans 
b
on ait toujours 
n
qui soit égal au nombre de fois où les éléments de 
a
commencent par 
list
. C'est bien ça ?

Exemple : 

a = [[1, 2, 3], [1, 2, 4], [1, 5, 6], [7, 8, 9]]
b = [([1], 3), ([7], 1), ([1, 2], 2), ([1, 5], 1), ([7, 8], 1), ([1, 2, 3], 1), ([1, 2, 4], 1), ([1, 5, 6], 1), ([7, 8, 9], 1)]

En terme d'algorithme je verrais bien un parcours d'arbre. Mon exemple pourrait se représenter comme ceci : 

     / \
    1   7
   / \   \
  2   5   8
 / \   \   \
3   4   6   9

Ton problème revient alors à calculer le nombre de feuilles du sous arbre dont la racine est déterminée par le chemin déjà parcouru de la liste.

Exemple, la liste [1] conduit à la racine 1, donc au sous-arbre {1, 2, 3, 4, 5, 6} qui contient 3 feuilles {3, 4, 6}.

Pour tout avoir, il faut récursivement construire au fur et à mesure la liste chemin de la racine, et faire la somme des résultats obtenus pour chaque sous arbre.

Exemple : f([1]) = f([1,2]) + f([1,5]) = f([1,2,3]) + f([1,2,4]) + f([1,5,6]) = 3
Remarque : en faisant ce parcours on n'a pas seulement trouvé [1], mais aussi calculé et trouvé le résultat de [1,2], [1,5], [1,2,3], [1,2,4] et [1,5,6] qu'il faut aussi enregistrer pour ne pas avoir à refaire les calculs.

Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^
0
Réponse 2 / 2
Habmra
 
Bonjour,
Oui c'est un peu ça, j'ai résolu mon problème, notamment j'ai arrivé de faire le comptage des nombres.
Il me reste de faire un arbre qui me parait n-aire( c'est un peu près comme votre arbre) ça c'est autre problème hahahaha
Pour :
"Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^"
Oui, ça fait 2 semaines je bosse dessus. c'est ne pas évident, je dois gérer aussi le temps de réponse de programme de calcul plus les tests de débogage.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Non ce n'est pas un arbre n-aire, car tu n'as apriori aucune limite "n" connue.
Toi ce que tu as c'est un arbre quelconque, mais la structure n'est pas très compliquée. 

public class Tree<E>
{
    private E node;
    private List<Tree<E>> children;
}
0
Habmra
 
Oui t'as raison c'est un arbre quelconque, c'est mieux développer une fonction successeur avant le parcours ça facilite la tâche dans ce cas
0

Discussions similaires

Tous les code possible de 0 à 9 (4 chiffres )
anonymeN1 -
anonymeN1 -

3 réponses