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

Question

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
Configuration: Windows 7 / Chrome 34.0.1847.137

KX · Answer

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

on ait toujours

qui soit égal au nombre de fois où les éléments de

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 ^^

Habmra · Answer

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.

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

2 réponses

Newsletters