LISP - Conjunto

O Common Lisp não fornece um tipo de dado definido. No entanto, ele fornece várias funções que permitem que as operações definidas sejam realizadas em uma lista.

Você pode adicionar, remover e pesquisar itens em uma lista, com base em vários critérios. Você também pode realizar várias operações de conjunto como: união, interseção e diferença de conjunto.

Implementando Conjuntos em LISP

Conjuntos, como listas, geralmente são implementados em termos de células cons. No entanto, por isso mesmo, as operações de conjuntos tornam-se cada vez menos eficientes quanto maiores se tornam os conjuntos.

o adjoinfunção permite que você construa um conjunto. Ele pega um item e uma lista que representa um conjunto e retorna uma lista que representa o conjunto que contém o item e todos os itens do conjunto original.

o adjoina função primeiro procura o item na lista fornecida; se for encontrado, ela retorna a lista original; caso contrário, ele cria uma nova célula cons com seucar como o item e cdr apontando para a lista original e retorna esta nova lista.

o adjoin função também leva :key e :testargumentos de palavra-chave. Esses argumentos são usados ​​para verificar se o item está presente na lista original.

Como a função adjoin não modifica a lista original, para fazer uma mudança na própria lista, você deve atribuir o valor retornado por adjoin à lista original ou pode usar a macro pushnew para adicionar um item ao conjunto.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

Quando você executa o código, ele retorna o seguinte resultado -

NIL
(2 1)
(2 1)
(3 2 1)

Verificando membros

O grupo de funções membro permite que você verifique se um elemento é membro de um conjunto ou não.

A seguir estão as sintaxes dessas funções -

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

Essas funções procuram na lista dada um determinado item que satisfaça o teste. Se nenhum item for encontrado, a função retornanil. Caso contrário, o final da lista com o elemento como o primeiro elemento é retornado.

A pesquisa é conduzida apenas no nível superior.

Essas funções podem ser usadas como predicados.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

Quando você executa o código, ele retorna o seguinte resultado -

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

Definir União

O grupo de funções de união permite que você execute a união de conjuntos em duas listas fornecidas como argumentos para essas funções com base em um teste.

A seguir estão as sintaxes dessas funções -

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

o unionA função recebe duas listas e retorna uma nova lista contendo todos os elementos presentes em qualquer uma das listas. Se houver duplicações, apenas uma cópia do membro será retida na lista devolvida.

o nunion A função executa a mesma operação, mas pode destruir as listas de argumentos.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Quando você executa o código, ele retorna o seguinte resultado -

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

Observe

A função de união não funciona como esperado sem :test-not #'mismatchargumentos para uma lista de três vetores. Isso ocorre porque, as listas são feitas de células cons e, embora os valores pareçam iguais para nós, aparentemente, ocdrparte das células não corresponde, portanto, não são exatamente iguais ao interpretador / compilador LISP. Esta é a razão; implementar grandes conjuntos não é aconselhável usar listas. Ele funciona bem para pequenos conjuntos.

Definir interseção

O grupo de interseção de funções permite que você execute a interseção em duas listas fornecidas como argumentos para essas funções com base em um teste.

A seguir estão as sintaxes dessas funções -

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

Essas funções recebem duas listas e retornam uma nova lista contendo todos os elementos presentes em ambas as listas de argumentos. Se qualquer uma das listas tiver entradas duplicadas, as entradas redundantes podem ou não aparecer no resultado.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Quando você executa o código, ele retorna o seguinte resultado -

(C)
(#(A B) #(5 6 7))
NIL

A função de interseção é a versão destrutiva da interseção, ou seja, ela pode destruir as listas originais.

Definir diferença

O grupo de funções de diferença de conjuntos permite que você execute diferenças de conjuntos em duas listas fornecidas como argumentos para essas funções com base em um teste.

A seguir estão as sintaxes dessas funções -

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

A função de diferença de conjunto retorna uma lista de elementos da primeira lista que não aparecem na segunda lista.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Quando você executa o código, ele retorna o seguinte resultado -

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))