Удалить даже появление элементов из списка с помощью Lisp или PROLOG

Question

Я должен удалить даже появление элемента из списка, используя LISP или PROLOG.

Вот пример.

вход: '(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2)

вывод: '(5 2 (3 () 5 (4 (2))))

Структура списка вывода остается прежней.

Спасибо за совет,

Answer 1

Поскольку это, кажется, домашнее задание, я приведу только указатель на решение:

• Просмотрите предикат REMOVE-IF в Common Lisp.(Он может делать не все, что вам нужно ...)
• Построить рекурсивный ходок.
• Подумайте, как вы будете передавать состояние назад и вперед.

КакКроме того, я настоятельно рекомендую опубликовать фрагмент вашей работы на сегодняшний день и задать конкретный вопрос.Обобщенный вопрос, такой как приведенный выше, говорит о том, что вы хотите, чтобы решение у вас на коленях.

Хорошо, это не домашняя работа.И я был интеллектуально заинтригован.Я решил это.

Это рекурсивный ходок.Если ваш 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))))

Answer 2

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

Answer 3

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

Вот [непроверенное] прологическое решение. В нем я просто поддерживаю два состояния 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     ).