递归的方案

Question

对名单

我已经试过很多次，但我仍然停留在这个问题上，这是我输入：

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

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

请帮忙!!!

Answer 1

一个非常漂亮和优雅的方式来解决这个问题，是使用哈希表来跟踪的在列表中找到对。这样，我们只需要在输入列表中的单个通：

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

Answer 2

我不知道为什么lambda是必要的;你可以直接用
(define (function arg1 arg2 ...) ...)(define (function arg1 arg2 ...) ...)
定义一个函数，但是，简而言之，问题在于汽车和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)))