Как проверить, что в списке есть разные объекты (это набор?) Или нет Схема - PullRequest
Новая
       7

Как проверить, что в списке есть разные объекты (это набор?) Или нет Схема

0 голосов
/ 26 апреля 2018

Я пытаюсь написать функцию в схеме, которая проверяет, является ли список набором или нет.

Алгоритм C будет выглядеть так: 

int count = sizeof(array) / sizeof(array[0]);

for (int i = 0; i < count - 1; i++) { 
    for (int j = i + 1; j < count; j++) {
        if (array[i] == array[j]) {
            //return false
        }
    }
}

(define set? (lambda (lst)

))

Ответы [ 3 ]

0 голосов
/ 26 апреля 2018

Я предполагаю, что вы хотите знать, как бы вы это делали, если бы, например, у языка еще не было набора типов данных (что делает Racket) и набора инструментов для работы с наборами, включая работу со списками как наборы. Итак, давайте заново изобретем вещи, которые уже существуют, начиная с функции, которая сообщает вам, если что-то происходит в списке (в реальной жизни это набор функций с именами, такими как member): 

(define (occurs? e l (test? eqv?))
  ;; does e occur in l, testing with test?
  (cond [(null? l)
         ;; empty lists have no members
         #f]
        [(test? e (first l))
         ;; if e is the first element of l then it's in l
         #t]
        [else
         ;; if e is in the rest of l it's in l
         (occurs? e (rest l) test?)]))

И теперь вы можете ответить на вопрос, является ли список множеством. Список является набором, если:

  • это пустой список;
  • первый элемент списка не встречается в остальной части списка, и остальная часть списка является набором.

И эту спецификацию можно превратить прямо в код: 

(define (list-set? l (test? eqv?))
  ;; is l a set?
  (if (null? l)
      ;; the empty list is a set
      #t
      ;; otherwise it is a set if ...
      (and
       ;; .. the first element of it does not occur in the rest of it ...
       (not (occurs? (first l) (rest l) test?))
       ;; ... and the rest of it is a set
       (list-set? (rest l) test?))))
0 голосов
/ 26 апреля 2018

По сути, у вас есть два курсора. i, который начинается в начале и идет к следующему элементу, и для каждого из тех, у кого есть j, начинается один рядом с i и продолжается до конца.

Вот как сделать цикл: 

(let name ((var 0) (var2 5))
  (if (> var var2)
      var
      (name (+ (* 2 var) 1) (+ var2 1))))

Поскольку здесь речь идет о списках, а списки представляют собой цепочки cons вместо индексов, вы просто используете привязки к индивидуальному cons для итерации: 

(define test '(1 2 3 4 5 6 7 8))
(let find-half ((hare test) (tortoise test))
  (if (or (null? hare)
          (null? (cdr hare)))
      tortoise
      (find-half (cddr hare) (cdr tortoise))))

Так как называется let? Это рекурсивная функция. Вышеуказанное совпадает с: 

(define test '(1 2 3 4 5 6 7 8))
(define (find-half hare tortoise)
  (if (or (null? hare)
          (null? (cdr hare)))
      tortoise
      (find-half (cddr hare) (cdr tortoise))))
(find-half test test)

Может быть проще написать решение C с рекурсией? Например. 

int fori (int i) {
  return i >= count - 1 ||
         forj(i, i+1) && fori(i+1); 
}

int forj (int i, int j) {
  return j >= count || 
        array[i] == array[j] && forj(i, j+1);
}

int result = fori(0);
0 голосов
/ 26 апреля 2018

Вы используете тег [racket], поэтому я предполагаю, что вы используете Racket. Вы можете использовать библиотечную функцию check-duplicates для проверки наличия дублирующих элементов. Вы можете использовать remove-duplicates для их удаления.

...