球拍：计算兄弟姐妹的数量

Question

将嵌套列表作为输入，我试图找到如何输出元素具有的 'siblings' 的数量。就树而言，有多少其他叶节点属于同一个parent/root节点。

我的代码给出了错误的输出（这是一个非常糟糕的代码），我不确定如何完全解决这个问题

(define (siblings lst n)
 (cond
     [(empty? lst) false]
     [(member? n lst) (sub1 (length lst))]
     [else (siblings (rest lst) n)]))

示例结果：如果给出 (list (list 2 1) 3 (list 4)) 和 3，产生 0

(列表 (列表 1 2 3) (列表 (列表 4 5 6 ))) 和 5 -> 2

Answer 1

您的代码必须做两件不同的事情：

找到包含n
计算该分支中兄弟姐妹的数量，并考虑其他分支从那里开始的可能性。

寻找包含n的分支，假设n只能出现一次：

(define (find-branch root n)
  (cond ((empty? root) empty)
        ((memq n root)
          root)
        ((list? (first root))
         (let ((subresult (find-branch (first root) n)))
           (if (not (empty? subresult))
               subresult
               (find-branch (rest root) n))))
        (else (find-branch (rest root) n))))

由于您使用的是 "Beginning Student,"，因此您可以从工具箱中取出所有工具。幸运的是，它仍然有 number?，所以如果可以安全地假设在这个赋值中任何不是数字的东西都是一个列表，你可以这样定义 list?：

(define (list? n) (not (number? n)))

给定您的示例树作为输入，它将 return:

(4 5 6)

以上示例在 rest 上重复使用了 memq 输入列表作为使用递归迭代相同列表的结果。

这是上面的一个更有效的版本，但是你不能在初级学生中实现它：

(define (find-branch root n)
  (cond ((empty? root) false)
        ((memq n root) root)
        (else (foldl (λ (a b)
                        (if (empty? a) b a))
                     empty
                     (map (λ (sublist)
                             (find-branch sublist n))
                       (filter list? root))))))

您将其结果传递给一个函数来计算兄弟姐妹的数量。我之前提供了一个可以在真实 Racket 中使用的版本，但不是教师使用的 Beginning Student 版本：

(define (count-siblings root mem)
  (count (λ (sib)
            (and (not (eq? sib mem))
                 (not (list? sib)))) root))

这是与 Beginning Student 兼容的版本：

(define (count-siblings lst n counter)
  (cond
     [(empty? lst) counter]
     [(and (not (list? (first lst)))
           (not (eq? n (first lst)))) 
      (count-siblings (rest lst) n (add1 counter))]
     [else (count-siblings (rest lst) n counter)]))

最后把两者放在一起：

(define (find/count-siblings root n)
   (count-siblings (find-branch root n) n 0))

球拍：计算兄弟姐妹的数量

racket: counting number of siblings

tree

nested

list

siblings

racket