リスト内で1つの数字が何回出現するかを調べる

Question

list A (1 2 1 1 2 3 3 4 4 4)私たちは新しいlist B ((1 . 30) (2 . 20) (3 . 20) (4 . 30))を得ることができましたか？ number_before_dotがリストA 'の％number_before_dotである場合。たとえば、リストAの％1はリストAの％1、リストAの20％は2です。 （1.30）は（cons 1 30）で作成できるペアです

Answer 1

私はあなたが望むと思うそうするためには、各要素に等しいリストのパーセンテージを計算します。あなたは "ユニーク"という言葉を使用しましたが、あなたのリストにはユニークな要素がないので少し混乱しています。これは、リスト(1 2 1 1 2 3 3 4 4 4)が「30％もの」で構成されているサンプル入力と出力に基づいています。

あなたはおおよそ以下の手順からなる再帰アルゴリズムにこれを打破することができます：入力リストが空の場合は空のリストを返し、

1. 。
2. それ以外の場合は、最初の要素を取得します。リストに何回出現したかを計算します。
3. パーセントを計算し、このパーセンテージで要素をconsにします。
4. リストのcdrから最初のアイテムのすべての出現を削除します。
5. この新しいリストでは、consのリストが再現され、(element . percentage)のペアがリストアップされます。

、最初の部分を行うのは、filterを使用できるようにするには：

> (filter (lambda (x) (eq? (car A) x)) A) 
(1 1 1) 

あなたのリストのAで、これはリスト(1 1 1)を返します。割合、全体のリストの要素の数で割る、または(length A)を計算し、100を掛けするには

> (length (filter (lambda (x) (eq? (car A) x)) A)) 
3 

：：私たちは、それが発生した回数を取得するために長さを使用することができます

> (* 100 (/ (length (filter (lambda (x) (eq? (car A) x)) A)) (length A))) 
30 

最終的なリストのペアを取得するには(car A)とconsこれは簡単です。第2工程を行うには

、我々はfilterの逆数であるremoveを使用することができます。それは、述語関数を満たしていない元のリストのすべての要素のリストを返します。

> (remove (lambda (x) (eq? (car A) x)) A) 
(2 2 3 3 4 4 4) 

これは、再帰的にリストしたいリスト。各ステップで、元のリスト（または元のリストの長さ）とこの新しいリストを持つ必要があることに注意してください。ですから、余分な引数を取るか、内部定義を定義することによって、何とかこれを再帰的プロシージャで利用できるようにする必要があります。

もっと効率的な方法があるかもしれませんが、それ以外の方法もありますが、これは私が質問を読むときに思いついた解決策でした。それが役に立てば幸い！

(define (percentages all) 
    (let ((len (length all))) ; pre-calculate the length 
    ;; this is an internal definition which is called at *** 
    (define (p rest) 
     (if (null? rest) 
      rest 
      ;; equal-to is a list of all the elements equal to the first 
      ;; ie something like (1 1 1) 
      (let ((equal-to (filter (lambda (x) (eq? (car rest) x)) 
            rest)) 
       ;; not-equal-to is the rest of the list 
       ;; ie something like (2 2 3 3 4 4 4) 
       (not-equal-to (remove (lambda (x) (eq? (car rest) x)) 
             rest))) 
      (cons (cons (car rest) (* 100 (/ (length equal-to) len))) 
        ;; recurse on the rest of the list 
        (p not-equal-to))))) 
    (p all))) ; *** 

Answer 2

質問式はrun-length encodingの考え方に非常に近いです。ランレングス符号化では、単純な戦略を使用できます。

1. ソート。
2. ランレングスエンコード。
3. ランレングスをスケーリングしてパーセンテージを取得します。

あなたは、このようなランレングス符号化を実装することができます：今、私たちはリストをソートするために何かを必要とする

(define (scale-cdr count-list total-count) 
    (define (normalize pr) 
    (cons (car pr) (/ (* 100 (cdr pr)) total-count))) 
    (map normalize count-list)) 

：

(define (run-length-encode lst) 
    (define (rle val-lst cur-val cur-cnt acc) 
    (if (pair? val-lst) 
     (let ((new-val (car val-lst))) 
      (if (eq? new-val cur-val) 
       (rle (cdr val-lst) cur-val (+ cur-cnt 1) acc) 
       (rle (cdr val-lst) new-val 1 (cons (cons cur-val cur-cnt) acc)))) 
     (cons (cons cur-val cur-cnt) acc))) 
    (if (pair? lst) 
     (reverse (rle (cdr lst) (car lst) 1 '())) 
     '())) 

とスケーリングがどのように見えます。私はちょうどラケットでsort機能を使用します（必要に応じて適応します）。リスト内の各番号の割合を計算する関数は次のとおりです。使用の

(define (elem-percent lst) 
    (scale-cdr (run-length-encode (sort lst <)) (length lst))) 

いくつかの例：

> (elem-percent '()) 
'() 
> (elem-percent (list 1 2 3 4 5)) 
'((1 . 20) (2 . 20) (3 . 20) (4 . 20) (5 . 20)) 
> (elem-percent (list 1 2 1 1)) 
'((1 . 75) (2 . 25)) 
> (elem-percent (list 1 2 1 1 2 3 3 4 4 4)) 
'((1 . 30) (2 . 20) (3 . 20) (4 . 30))