当前位置：文江博客话题详情

lisp prolog

使用 Lisp 或 PROLOG 从列表中删除偶数出现的元素

发布于 2024-11-30 06:34:50 字数 178 浏览 1 评论 0 原文

我必须使用 LISP 或 PROLOG 从列表中删除甚至出现的元素。

这是一些例子。

输入：'(5 2 (3 5 (3)) 5 (4 2 (2 4))) 5 2)

输出：'(5 2 (3 () 5 (4 (2))))

输出列表的结构保持不变相同。

感谢您的建议，

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

定格我的天空 2024-12-07 06:34:50

由于这似乎是一项作业，因此我将仅提供解决方案的指针：

查看 REMOVE-IF 谓词。（它可能无法完成您需要的所有操作...）
构建一个递归步行器。
考虑如何来回传递状态。

顺便说一句，我强烈建议您发布您迄今为止的工作片段并提出一个具体问题。诸如上述之类的普遍问题似乎表明您希望找到一个解决方案。

好吧，这不是家庭作业。我对智力产生了兴趣。我解决了。

这是一个递归步行器。如果你的 Lisp 有 TCO，它应该可以转化为 TCO。

您可以在循环中执行此操作，但这需要维护堆栈列表来处理“进入列表”情况。

我不声称有一个惯用的解决方案。

(defparameter input '(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2))

(defparameter output '(5 2 (3 () 5 (4 (2)))))

(defun remove-every-other-appearence (list &optional (hash-table nil))
  (when list                             ; termination condition
    ;(format t "~%~a~&" list)
    (unless hash-table                     ; if it's the first time
      ;(format t "creating hash table~&")
      (setf hash-table (make-hash-table))) ; create a hash table
    (let ((eut (car list)))                ; element under test
      ;(format t "eut: ~a~&" eut)
      (cond
        ((consp eut)                      ;Recursion time, it's a list.
         ;(format t "Recursing~&")
         (cons
          (remove-every-other-appearence eut hash-table)
          (remove-every-other-appearence (cdr list) hash-table)))
        (t                                ;Otherwise...
                                        ; Increment seen counter by 1
         (setf (gethash eut hash-table 0) 
               (1+ (gethash eut hash-table 0)))
         (cond
           ((evenp (gethash eut hash-table))
             (remove-every-other-appearence (cdr list) hash-table))
                                        ;ignore the element
           ((oddp (gethash eut hash-table))
                                        ; if this is the odd occurance
                                        ;cons the element back onto the rest of the list
            (cons eut (remove-every-other-appearence (cdr list) hash-table)))           
           (t
            (error "This integer is neither even nor odd. We're in trouble"))))))))

* input

(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2)
* (remove-every-other-appearence input)

(5 2 (3 NIL 5 (4 (2))))
* output

(5 2 (3 NIL 5 (4 (2))))

Since this appears to be a homework, I am going to provide only a pointer to the solution:

Review the REMOVE-IF predicate in Common Lisp. (It may not do everything you need...)
Build a recursive walker.
Consider how you will pass the state back and forth.

As an aside, I highly recommend posting a snippet of your work to date and asking a specific question. A generalized question such as the above seems to suggest you want a solution dropped in your lap.

Okay, it's not homework. And I got intellectually intrigued. I solved it.

It's a recursive walker. If your Lisp does TCO, it should be transformable into a TCO.

You can do it in a loop, but that would require maintaining a stack list to handle the "go into list" case.

I make no claims to an idiomatic solution.

(defparameter input '(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2))

(defparameter output '(5 2 (3 () 5 (4 (2)))))

(defun remove-every-other-appearence (list &optional (hash-table nil))
  (when list                             ; termination condition
    ;(format t "~%~a~&" list)
    (unless hash-table                     ; if it's the first time
      ;(format t "creating hash table~&")
      (setf hash-table (make-hash-table))) ; create a hash table
    (let ((eut (car list)))                ; element under test
      ;(format t "eut: ~a~&" eut)
      (cond
        ((consp eut)                      ;Recursion time, it's a list.
         ;(format t "Recursing~&")
         (cons
          (remove-every-other-appearence eut hash-table)
          (remove-every-other-appearence (cdr list) hash-table)))
        (t                                ;Otherwise...
                                        ; Increment seen counter by 1
         (setf (gethash eut hash-table 0) 
               (1+ (gethash eut hash-table 0)))
         (cond
           ((evenp (gethash eut hash-table))
             (remove-every-other-appearence (cdr list) hash-table))
                                        ;ignore the element
           ((oddp (gethash eut hash-table))
                                        ; if this is the odd occurance
                                        ;cons the element back onto the rest of the list
            (cons eut (remove-every-other-appearence (cdr list) hash-table)))           
           (t
            (error "This integer is neither even nor odd. We're in trouble"))))))))

* input

(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2)
* (remove-every-other-appearence input)

(5 2 (3 NIL 5 (4 (2))))
* output

(5 2 (3 NIL 5 (4 (2))))

回复收藏 0 原文

小姐丶请自重 2024-12-07 06:34:50

FWIW，你的问题陈述相当不清楚。

据我了解这个问题，问题是你有一个任意的“树”，其非叶节点是列表，其叶节点是其他东西。可以说是“列表的列表”。您希望将其视为叶节点的逻辑平面序列，对其进行迭代并删除所有其他叶节点而不改变“树”的整体形状，例如唯一改变的是任何给定节点上悬挂的叶子数量。

由此，给定以下输入，您将实现相应的输出：

input:  []
output: []

input:  [a,b,c,d]
output: [a,c]

input:  [a,[],b,c,d]
output: [a,[],c]

input:  [a,[b],c,d]
output: [a,[],c]

input:  [a,[b,c,d,e],f,g]
output: [a,[c,e],g]

input:  [a,[b,[],[c,d,[e,f,g],h],i],j]
output: [a,[[],[c,[e,g]],i]]

这是一个[未经测试的] prolog 解决方案。在其中，我只维护两个状态，keep 和 remove 并根据需要在它们之间切换。您可以免费获得奇数/偶数：这仅取决于您启动机器的状态。

应该注意的是，如果传入的数据结构包含任何未绑定/非统一的变量，您就不可能获得正确的结果。不需要的统一会导致问题。需要添加保护子句才能正确处理它们。

% ====================
% The public interface
% ====================
remove_even( Xs , Ys ) :- remove_every_other_node( keep   , _ , Xs , [] , Ys ).
remove_odd(  Xs , Ys ) :- remove_every_other_node( remove , _ , Xs , [] , Ys ).

%------------------
% The core iterator
%------------------
remove_every_other_node( S , S , [] , T , List ) :-
  reverse(T,List)
  .
remove_every_other_node( S , N , [X|Xs] , T , List ) :-
  process_node( S, S1 , X , T , T1 ) ,
  remove_every_other_node( S1 , N , Xs , T1 , List )
  .

%----------------------
% The list node handler
%----------------------
process_node( S , S , []     , T , [[]|T] ).
process_node( S , N , [X|Xs] , T , [L1|T] ) :-
  remove_every_other_node( S , N , [X|Xs] , [] , L1)
  .
process_node( keep   , remove , X , T , [X|T] ).
process_node( remove , keep   , X , T , T     ).

FWIW, your problem statement is rather unclear.

As I understand the question, the problem is that you have an arbitrary "tree", the non-leaf nodes of which are lists and the leaf nodes of which are something else. A "list of lists" as it were. You would like to view that as a logical flat sequence of leaf nodes, iterate over that and remove every other leaf node without altering the overall shape of the "tree", such that the only thing that changes is the number of leaves hanging from any given node.

From that, given the following inputs, you'd realize the corresponding outputs:

input:  []
output: []

input:  [a,b,c,d]
output: [a,c]

input:  [a,[],b,c,d]
output: [a,[],c]

input:  [a,[b],c,d]
output: [a,[],c]

input:  [a,[b,c,d,e],f,g]
output: [a,[c,e],g]

input:  [a,[b,[],[c,d,[e,f,g],h],i],j]
output: [a,[[],[c,[e,g]],i]]

Here's an [untested] prolog solution. In it, I just maintaining two states, keep and remove and toggle between them as needed. You get odd/even for free: it just depends on the state in which you start the machine.

It should be noted that if the data structure passed in contains any unbound/non-unified variables, you're unlike to get correct results. Unwanted unification causes problems. Guard clauses would need to be added to properly handle with them.

% ====================
% The public interface
% ====================
remove_even( Xs , Ys ) :- remove_every_other_node( keep   , _ , Xs , [] , Ys ).
remove_odd(  Xs , Ys ) :- remove_every_other_node( remove , _ , Xs , [] , Ys ).

%------------------
% The core iterator
%------------------
remove_every_other_node( S , S , [] , T , List ) :-
  reverse(T,List)
  .
remove_every_other_node( S , N , [X|Xs] , T , List ) :-
  process_node( S, S1 , X , T , T1 ) ,
  remove_every_other_node( S1 , N , Xs , T1 , List )
  .

%----------------------
% The list node handler
%----------------------
process_node( S , S , []     , T , [[]|T] ).
process_node( S , N , [X|Xs] , T , [L1|T] ) :-
  remove_every_other_node( S , N , [X|Xs] , [] , L1)
  .
process_node( keep   , remove , X , T , [X|T] ).
process_node( remove , keep   , X , T , T     ).

回复收藏 0 原文

北凤男飞 2024-12-07 06:34:50

(defun rea (tree)
  (let ((table (make-hash-table)))
    (labels ((fn (x)
               (unless (and x (atom x) (evenp (incf (gethash x table 0))))
                 (list (if (atom x) x (mapcan #'fn x))))))
      (car (fn tree)))))

(defun rea (tree)
  (let ((table (make-hash-table)))
    (labels ((fn (x)
               (unless (and x (atom x) (evenp (incf (gethash x table 0))))
                 (list (if (atom x) x (mapcan #'fn x))))))
      (car (fn tree)))))

回复收藏 0 原文

~没有更多了~