删除子列表中的元素

Question

我有一个表格列表：

((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1)))

此列表表示形式为 ("node" ("edges")) 的图形。我该如何编写一个过程，该过程采用表示节点的值（例如“1”），并从图中删除该节点。例如： (delete-node n g) with input 5 and '((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 (5)) (5 (4))) 应该输出：

((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 ()))

从上面的例子可以看出，节点和添加到该节点的任何边都必须被删除。到目前为止，我的代码如下：

(define graph '((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 (5)) (5 (4))))

;...Other procedures not shown...

(define (delete-node n g)
    (define (delete ls item)
      (cond ((null? ls) nil)
            ((pair? (car ls))
             (cons (delete (car ls) item) (delete (cdr ls) item)))
            ((equal? (car ls) item) (delete (cdr ls) item))
            (else (cons (car ls) (delete (cdr ls) item)))))
      (delete (filter (lambda (x) (not (eq? (car x) n))) g) n))

(delete-node 5 graph)

上面的代码有效，但是有没有更有效的方法呢？

Answer 1

使用高级函数的可能定义如下：

(define (delete-node n g)
  (map (lambda(x) (list (car x) (filter (lambda(x) (not (= x n))) (cadr x))))
       (filter (lambda(x) (not (= (car x) n))) g)))

(delete-node 5 '((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 (5)) (5 (4))))
       ; produces ((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 ()))

使用递归函数的稍微更有效的解决方案如下：

(define (delete-node n g)
  (cond ((null? g) '())
        ((= (caar g) n) (delete-node n (cdr g)))
        (else (cons (list (caar g) (filter (lambda(x) (not (= x n))) (cadar g)))
                    (delete-node n (cdr g))))))

如果图很大而且你知道它的结构是正确的，知道只有一个节点的输出弧可以等于 n，一个更有效的版本可能如下：

(define (delete-node n g)
  (define (delete-edge edges)
    (cond ((null? edges) '())
          ((= (car edges) n) (cdr edges))  ; stop recursion when the edge is found
          (else (delete-edge (cdr edges)))))
  (cond ((null? g) '())
        ((= (caar g) n) (delete-node n (cdr g)))
        (else (if (member n (cadar g) =)
                  (cons (list (caar g) (delete-edge (cadar g)))
                        (delete-node n (cdr g)))
                  (cons (car g) (delete-node n (cdr g)))))))

请注意，测试 (member n (cadar g) =) 是为了避免在 n 不存在时复制边缘列表。

Answer 2

不确定我是否正确理解您的问题 - 这符合您的需求吗？

(define (delete-node node graph)
  (define node-1 (car node))
  (define node-2 (cdr node))
  (let iter ((graph graph) (result '()))
    (if (null? graph)
        (reverse result)
        (let* ((head (car graph)) (head-1 (car head)) (head-2 (cadr head)))
          (iter (cdr graph)
                (cons (cond
                        ((eqv? head-1 node-1) (list head-1 (remove node-2 head-2)))
                        ((eqv? head-1 node-2) (list head-1 (remove node-1 head-2)))
                        (else         head))
                      result))))))

测试：

> (delete-node '(2 . 3) '((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1))))
'((1 (3 2 4)) (2 (1)) (3 (1)) (4 (1)))
> (delete-node '(1 . 2) '((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1))))
'((1 (3 4)) (2 (3)) (3 (2 1)) (4 (1)))

删除子列表中的元素

Removing elements within sublists

scheme