Comment implémenter un compteur pour chaque nombre dans une liste avec Scheme?

Question

Ok Je veux compter le nombre de fois que [nombre] est apparu dans une liste en utilisant Scheme.

Comment puis-je faire cela? Je voudrais aussi stocker le compteur du nombre donné et reconstruire une nouvelle liste.

Par exemple, j'ai la liste suivante ((1 2)(2 5)(5 7)(7 8)(6 8)(4 6)(3 4)(1 3)(4 8))

je pense d'abord aplatir la liste, puis définissez un compteur pour chaque numéro (ne savent pas comment le faire). Et puis reconstruire une nouvelle liste correspondant au numéro d'origine. (Cela peut être difficile? Je dois stocker une variable temporaire?)

Dites de cet exemple le numéro 1 est apparu deux fois, le numéro 2 est apparu deux fois, le numéro 3 deux fois etc ... donc je voudrais recréer une nouvelle liste à quelque chose comme ceci:

(1 2) (2 2) (3 2) (4 3) (5 2) (7 2) (6 2) (8 3) 

aucune idée comment je peux y parvenir?

Mise à jour:

Je pensais à mettre en œuvre quelque chose comme un contre-incrément d'aide cela?

(define inc-counter 
    (let ((counter 0)) 
     (lambda() (set! counter (+ counter 1))))) 

Answer 1

Utilisez un paramètre d'accumulateur pour aplatir qui maintient une liste d'association de combien de fois chacun est apparu. De cette façon, vous aurez toutes les données dont vous avez besoin à chaque fois dans la boucle.

Par exemple, vous pourriez écrire factoriel comme ceci:

(define (factorial num accum)
  (if (= num 0) accum (factorial (- num 1) (* accum num)))

Et l'appeler avec (factoriel 10 1). A la fin, la valeur de l'accumulateur est le résultat de la fonction. Dans votre exemple, vous écririez une petite fonction d'aide qui appellerait aplatir et garder une trace du nombre de fois que chaque nombre est apparu.

Answer 2

Peut-être pas la solution la plus efficace, mais je pense que vous pourriez y parvenir en partition en utilisant la première liste jusqu'à ce qu'il n'y ait plus d'éléments dans la liste. La liste des éléments incorporés serait alors tous les nombres de la liste qui étaient les mêmes que le premier nombre. Ce processus pourrait être répété sur la liste des éléments externes jusqu'à ce qu'il n'y ait plus d'éléments dans la liste.

Answer 3

Vous pouvez utiliser une table de hachage mappant le nombre à son nombre d'occurrences. Créez-le avec (make-hash).

Answer 4

Un bon bonne réponse dépend principalement de votre mise en œuvre (modulo R6RS). Dans le cas du schéma PLT, voici une définition rapide qui fait cela. Cela évite d'aplatir la liste - vous avez seulement besoin de scanner chaque élément, donc il ne sert à rien de construire une nouvelle copie lorsque l'analyse d'un arbre est si simple. De plus, cette fonction trie la liste résultante (puisque tout sera brouillé à sa sortie de la table de hachage). Même si vous utilisez une implémentation complètement différente, il devrait être facile à traduire:

(define (counts x) 
    (define t (make-hash)) 
    (define (scan x) 
    (if (list? x) 
     (for-each scan x) 
     (hash-set! t x (add1 (hash-ref t x 0))))) 
    (scan x) 
    (sort (hash-map t list) < #:key car)) 

(Notez, d'ailleurs, que si c'est tout type de question HW, alors ce code est beaucoup trop pratique pour être utile comme réponse ...)