1

我已经尝试了很多次，但我仍然陷入这个问题，这是我的输入：

 (define *graph*
  '((a . 2) (b . 2) (c . 1) (e . 1) (f . 1)))

我希望输出是这样的： ((2 ab) (1 cef))

这是我的代码：

(define group-by-degree
  (lambda (out-degree)
    (if (null? (car (cdr out-degree)))
        'done
        (if (equal? (cdr (car out-degree)) (cdr (car (cdr out-degree))))
            (list (cdr (car out-degree)) (append (car (car out-degree))))
            (group-by-degree (cdr out-degree))))))

你能告诉我我做错了什么吗，因为我的代码输出是（2 a）。然后我认为我的代码的想法是正确的。

请帮忙！！！

4

2 回答 2

2

解决这个问题的一个非常好的和优雅的方法是使用哈希表来跟踪列表中找到的对。通过这种方式，我们只需要对输入列表进行一次传递：

(define (group-by-degree lst)
  (hash->list
   (foldl (lambda (key ht)
            (hash-update
             ht
             (cdr key)
             (lambda (x) (cons (car key) x))
             '()))
          '#hash()
          lst)))

结果将以与问题中显示的顺序不同的顺序出现，但它是正确的：

(group-by-degree *graph*)
=> '((1 f e c) (2 b a))

如果输出列表中的顺序有问题，请尝试使用此方法，它的效率低于上一个答案，但输出将与问题中的相同：

(define (group-by-degree lst)
  (reverse
   (hash->list
    (foldr (lambda (key ht)
             (hash-update
              ht
              (cdr key)
              (lambda (x) (cons (car key) x))
              '()))
           '#hash()
           lst))))

(group-by-degree *graph*)
=> '((2 a b) (1 c e f))
于 2013-11-04T02:40:03.100 回答
-1

我不知道为什么需要 lambda；您可以直接使用
(define (function arg1 arg2 ...) ...)
That 定义一个函数，但是，简单地说，问题是汽车和 cdrs 搞砸了。我找不到一种方法来调整您的解决方案以使其正常工作，但这是一个有效的实现：

; appends first element of pair into a sublist whose first element 
; matches the second of the pair
(define (my-append new lst) ; new is a pair
  (if (null? lst)
    (list (list (cdr new) (car new)))

    (if (equal? (car (car lst)) (cdr new))
      (list (append (car lst) (list (car new))))
      (append (list (car lst)) (my-append new (cdr lst)))
    )
  )
)

; parses through a list of pairs and appends them into the list
; according to my-append
(define (my-combine ind)
  (if (null? ind)
    '()
    (my-append (car ind) (my-combine (cdr ind))))
)

; just a wrapper for my-combine, which evaluates the list backwards
; this sets the order right
(define (group-by-degree out-degree)
  (my-combine (reverse out-degree)))
于 2013-11-04T00:13:43.180 回答