Функция Scheme, которая проверяет список на наличие дубликатов

Question

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

Сначала мне нужно проверить, пустой ли это список.Итак, у меня есть ...

(define (checkDupe mylist)
  (if (null? mylist)
      ()
      (checkDupeB mylist)
  )
)

Затем у меня есть такая "двойная рекурсия", когда я проверяю первое число по остальной части списка, а затем второе число по остальной части спискаи так далее, и когда он находит совпадение, он выплевывает #t, если он достигает конца и не находит совпадения, результат функции равен #f.Проблема в том, что я просто не могу обернуться вокруг этой рекурсии.Это вопрос домашнего задания, но я искренне заинтересован в изучении этого материала.

Может ли кто-нибудь подсказать мне код и помочь мне разобраться с этим?

Answer 1

Вот это один из способов

(define (has-duplicates? lst) 
  (cond
     [(empty? lst) #f] 
     [(not (not (member (first lst) (rest lst)))) #t]
     [else (has-duplicates? (rest lst)) ])) 

Answer 2

Повторная проверка всего списка для каждого участника для проверки на наличие дубликатов может быть дорогой - O (n ^ 2).Проверка на смежные дубликаты намного дешевле - O (n).Если вы не возражаете против изменения порядка элементов в списке, вы можете сделать все дубликаты смежными, сначала отсортировав список.Список должен состоять из элементов, которые могут сравниваться некоторым оператором>.

(define (remove-duplicates xs)
  (fold-right cons-if-not-duplicate '() (sort xs >)))

Преимущество этого подхода состоит в том, что он опирается на стандартный оператор сворачивания, а не на пользовательскую рекурсию.Поскольку это домашнее задание, я опускаю определение cons-if-not-duplicate.

Answer 3

Полагаю, это домашнее задание. Это простая процедура, но вы пропускаете регистр в своем навигационном потоке, так как необходимо рассмотреть три варианта:

1. Что будет, если список пуст? это означает, что в нем нет дубликатов
2. Что происходит, если текущий элемент списка существует где-то в остальной части списка? тогда это означает, что в списке есть дубликат (подсказка: процедура member может быть полезна)
3. Если ничего из вышеперечисленного не соответствует действительности, переходите к следующему элементу

В качестве дополнительной помощи, вот общая идея, заполните пробелы:

(define (checkDupe mylist)
  (cond ((null? myList) ???) ; case 1
        (??? #t)             ; case 2
        (else ???)))         ; case 3

Answer 4

Это мое решение, которое, хотя и не проверено, должно работать,

(define rmdup
   (lambda list
      (cond
         ((null? list) '())
         ((eq? (car list) (car (cdr list)) (rmdup(cdr list)))
          (else( cons (car list) (rmdup(cdr list)))))))

Алгоритм вслух: если начальная машина равна следующей машине?Измените начальную настройку и перейдите снова, либо сохраните ее, затем продолжите.Таким образом, мы сохраняем только уникальные копии, а не что-либо с соседом или сестрой

Answer 5

Существует несколько способов решения проблемы. Вот предложение.

1. написать вспомогательную функцию (is-element-in-list? X l), который возвращает true, если x находится в списке l, и false в противном случае.

2. Заполните пробелы в

   (define (contains-duplicate? l)
      (cond [(list? l) (or <check whether (first l) is in (rest l)>
                           <check where (rest l) contains a duplicate> )
            [else false]))