遞歸的方案

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