Как найти необычные предметы в списке (взаимоисключающие) - PullRequest
Новая
       36

Как найти необычные предметы в списке (взаимоисключающие)

0 голосов
/ 27 мая 2018

Мне было поручено написать функцию схемы, которая может создавать новый список, содержащий элементы, которые существуют только в одном из двух входных списков.Мне удалось создать рабочее решение: 

(define remove
  (lambda (l item)
    (filter (lambda (x) (not (equal? x item))) l)))

(define uncommon_list
  (lambda (list1 list2)
    (cond 
      ((null? list2) list1)
      ((null? list1) list2)
      ((memv (car list1) list2)
       (uncommon_list (cdr list1) (remove list2 (car list1))))
      (else 
       (append (list (car list1)) (uncommon_list (cdr list1) list2))))))

Однако я чувствую, что слишком усложняю это, а сложность O не велика?Любые указатели, чтобы сделать это лучше, было бы здорово!Спасибо

Ответы [ 2 ]

0 голосов
/ 27 мая 2018

Для наилучшего большого O, то есть O (n), вам нужно создать наборы, а в Scheme это означает хеш-таблицы.Решение состоит в том, чтобы обновить хеш, чтобы знать, был ли он найден в первом, втором или обоих списках.Список тогда сделан из элемента, который не в обоих: 

#!r6rs

(import (rnrs base)
        (srfi :69))

(define (uncommon-elements l1 l2)
  (define hash (make-hash-table eqv?))
  (define (update-elements proc default lst)
    (for-each
     (lambda (e)
       (hash-table-update! hash e proc (lambda () default)))
     lst))

  (update-elements values 1 l1)
  (update-elements (lambda (e) (if (= e 2) 2 3)) 2 l2)
  (hash-table-fold hash
                   (lambda (k v acc)
                     (if (= v 3)
                         acc
                         (cons k acc)))
                   '()))

(uncommon-elements '(1 2 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)

(uncommon-elements '(1 1 2 2 3 3 4 5) '(3 4 5 6 7 8))
; ==> (1 2 6 7 8)
0 голосов
/ 27 мая 2018 
(define a_minus_b(
        lambda (lista listb) (
            cond
                ((null? lista) `())
                ((memv (car lista) (cdr lista)) (a_minus_b (cdr lista) listb))
                ((memv (car lista) listb) (a_minus_b (cdr lista) listb))
                (else (cons (car lista) (a_minus_b (cdr lista) listb)))
        )
    )
)

(define symmetric_diff(
        lambda (list1 list2) (
            append (a_minus_b list1 list2) (a_minus_b list2 list1)
        )
    )
)
...