카디널리티를 기반으로 숫자 목록에서 쌍을 만드는 방법은 무엇입니까?

Question

목록이 '(1 2 1 1 4 5)이고 출력 목록을 '((1 3)(2 1)(4 1)(5 1))으로 지정하고 싶습니다. 작은 코드를 작성했지만 각 숫자의 카디널리티를 계산 한 다음 목록에 쌍으로 넣는 방법에 익숙합니다. 아무도 내 코드를보고 몇 가지 아이디어를 주실 수 있습니까? 감사.

(define set2bags 
    (lambda (randlist) 
    (cond ((null? randlist) '()) 
      (else 
      (sort randlist) 
      (makepairs randlist))))) 

(define makepairs 
    (lambda (inlist) 
    (let ((x 0)) ((newlist '())) 
     (cond ((zero? (car inlist)) '()) 
      (else 
      (eq? (car inlist)(car (cdr inlist))) 
      (+ x 1) 
      (makepairs (cdr inlist)) 
      (append newlist (cons (car inlist) x))))))) 

Answer 1

현재 해결책이 잘못되었습니다. 컴파일되지 않습니다. 의 입력 목록 통과에 대한 named let를 사용하여, 처음부터 다시 시작하자 : 이제

(define set2bags 
    (lambda (randlist) 
    (cond ((null? randlist) '()) 
      (else (makepairs (sort randlist >)))))) 

(define makepairs 
    (lambda (inlist) 
    (let loop ((lst inlist) 
       (prv (car inlist)) 
       (num 0) 
       (acc '())) 
     (cond ((null? lst) 
      (cons (list prv num) acc)) 
      ((= (car lst) prv) 
      (loop (cdr lst) prv (add1 num) acc)) 
      (else 
      (loop (cdr lst) (car lst) 1 (cons (list prv num) acc))))))) 

을가 예상대로 작동합니다

(set2bags '(1 2 1 1 4 5)) 
=> '((1 3) (2 1) (4 1) (5 1)) 

이 트릭은 카디에 대한 카운터를 유지하고있다

(나는 num라고 불렀다) 동일한 이전 요소 (이름이 prv 인 경우)가 현재 요소와 동일한 경우 해당 요소를 증가시킵니다. 다른 요소를 찾을 때마다 출력 목록 (acc)에 새 쌍을 추가하고 이전 요소와 카운터를 재설정합니다.

Answer 2

코드는 적절한 형식 지정 없이는 읽기가 어렵습니다. if로 읽는 것이 더 쉬운 두 개의 분기 cond에 주목합니다.

set2bags의 else 절에서 (randlist 정렬)을 호출하지만 그대로 두십시오. 당신은 실제로 다음 s-expression (makepairs (sort randlist))에서 이것을 사용하고 싶습니다.

지금까지는 꽤 좋은 생각이었습니다.

이제 메이크 페어에서는 더 나은 추상화가 있어야합니다. 예를 들어, 변수를 첫 번째와 다른 것으로 먼저 말하십시오. inlist가 null 인 경우 함수는 null 목록이어야합니다. 그렇지 않으면 car가 like-first의 자동차 목록이고 like-first의 길이 인 cdr과 cdr이 makepairs를 호출 한 결과 인 쌍입니다. 달리 - 첫 번째 목록

(define (makepairs inlist) 
(let ((like-first (filter (lambda (x) (equal? x (car inlist)) inlist)) 
     (unlike-first (filter (lambda (x) (not (equal? x (car inlist))) inlist))) 
    (if (null? inlist) 
     '() 
     (cons (list (car inlist) (length like-first)) (makepairs unlike-first))))) 

더 일종의 자신의 구현이있는 경우 effecient 버전

(define (makepairs inlist) 
(if (null? inlist) 
    '() 
    (let loop ((firsts (list (car inlist))) 
       (but-firsts (cdr inlist))) 
     (if (or (null? but-firsts) 
       (not (equal? (car firsts) (car but-firsts)))) 
      (cons (list (car firsts) (length firsts)) 
       (makepairs but-firsts)) 
      (loop (cons (car but-firsts) firsts) (cdr but-firsts)))))) 

]=> (makepairs (list 1 1 1 2 4 5)) 

;Value 17: ((1 3) (2 1) (4 1) (5 1)) 

, 머지 소트는 당신이 최고의 effeciency의 병합 부분에이 권리를 쓸 수 있다고 말한다.

(define (set2bags lst) 
(mergesort2bags lst <)) 

(define (mergesort2bags lst pred) 
(let* ((halves (divide-evenly lst)) 
     (first-half (car halves)) 
     (other-half (cadr halves))) 
(cond ((null? lst) '()) 
     ((null? (cdr lst)) (list (list (car lst) 1))) 
     (else 
     (merge-bags 
      (mergesort2bags first-half pred) 
      (mergesort2bags other-half pred) 
      pred))))) 

(define (divide-evenly lst) 
(let loop 
    ((to-go lst) 
    (L1 '()) 
    (l2 '())) 
    (if (null? to-go) 
     (list L1 L2) 
     (loop (cdr to-go) (cons (car to-go) L2) L1)))) 

(define (merge-bags L1 L2 pred) 
(cond ((null? L1) L2) 
     ((null? L2) L1) 
     ((pred (caar L1) (caar L2)) 
     (cons (car L1) (merge-bags (cdr L1) L2 pred))) 
     ((equal? (caar L1) (caar L2)) 
     (cons (list (caar L1) (+ (cadar L1) (cadar L2))) 
       (merge-bags (cdr L1) (cdr L2) pred))) 
     (else (cons (car L2) (merge-bags L1 (cdr L2) pred))))) 

(mergesort2bags (list 1 2 1 1 4 5) <) 

;Value 46: ((1 3) (2 1) (4 1) (5 1)) 

나는이 방법이 많은 반복을 통해 매우 큰 데이터 세트에 대해 생각하고 있습니다.