2

我有一个列表'(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)))))))
4

2 回答 2

2

您当前的解决方案不正确 - 它甚至无法编译。让我们从头开始，使用一个命名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）并重置前一个元素和计数器。

于 2013-08-08T03:26:57.370 回答
0

如果没有正确的格式，您的代码很难阅读。我注意到一个两个分支条件，它更容易阅读为 if。

在 set2bags 的 else 子句中，您调用 (sort randlist) 但保持原样。您实际上想在下一个 s 表达式中使用它 (makepairs (sort randlist))

到目前为止，这是一个不错的主意。

现在在 makepairs 中你应该有更好的抽象，比如让变量先喜欢和不喜欢。如果 inlist 为 null，则该函数应该是 null 列表，否则它是与 car 是 like-first 的 car 列表和 like-first 的长度的对，而 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)))))

更高效的版本

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

如果您有自己的排序实现，比如合并排序，您可以将其写入合并部分以获得最佳效率。

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

我正在考虑对于具有大量重复的非常大的数据集，这种方法会得到回报。

于 2013-08-08T03:24:00.447 回答