3

Aを保持するリストがある場合、 number_after_dotがリスト内のnumber_before_dotのパーセンテージになるように(1 2 1 1 2 3 3 4 4 4)、どのようにして新しいリストを取得できますBか。((1 . 30) (2 . 20) (3 . 20) (4 . 30))A

たとえば1、リストの30％、リストAの 220％Aなどです。

(1 . 30)によって作ることができるペアです(cons 1 30)

4

2 に答える 2

2

あなたがやりたいのは、各要素に等しいリストのパーセンテージを計算することだと思います。「一意」という単語を使用しましたが、リストに一意の要素がないため、少し混乱します。これは、サンプルの入力と出力に基づいており、リスト(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を使用して、発生する回数を取得できます。

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

パーセンテージを計算するには、リスト全体の要素数で割るか(length A)、100を掛けます。

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

最終的なリストのペアを取得するcons要素を使用すると、これを簡単に行うことができます。(car A)

2番目のステップを実行するには、次removeの逆を使用できます。これはfilter、述語関数を満たさない元のリストのすべての要素のリストを返します。

> (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))) ; ***
于 2011-01-25T17:42:43.097 に答える
2

質問の定式化は、ランレングスエンコーディングの概念に非常に近いものです。ランレングスエンコーディングに関しては、次の簡単な戦略を使用できます。

  1. 選別。
  2. ランレングスエンコード。
  3. 実行長をスケーリングしてパーセンテージを取得します。

次のようなランレングスエンコーディングを実装できます。

(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 '()))
      '()))

スケーリングは次のようになります。

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

次に、リストを並べ替える何かが必要です。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))
于 2011-03-26T14:15:06.413 に答える