Обработка двух сложных входов (удаление списков дублирующих символов в списке) - PullRequest
Новая
       3

Обработка двух сложных входов (удаление списков дублирующих символов в списке)

1 голос
/ 29 декабря 2010

Этот вопрос из упражнения 17.6.5 из htdp . Мне нужно несколько советов о том, как определить, является ли пара символов уникальной в списке списков.

Вот что я получил до сих пор: 

;; pair : symbol, list of symbols -> list of list of symbols

;; an auxiliary function that returns a list of possibly non-unique 
;; lists of pairings from a name (symbol) and a list of names (list of symbols).

;; output from (pair 'Alice '(Bob Charlie))
;; (list 
;; (list 'Alice 'Bob) (list 'Bob 'Alice) (list 'Alice 'Charlie)
;; (list 'Charlie 'Alice) (list 'Bob 'Charlie) (list 'Charlie 'Bob))

(define (pair name alist)
  (cond
  [(empty? alist) empty]

  [(cons? alist) (append (pair name (first alist))
                         (pair name (rest alist))
                         (pair (first alist) (rest alist)))]

  [else (list (append (list name)(list alist))
              (append (list alist)(list name)))]))

Если эта функция применяется к вопросу (5 имен), она выдает 30 списков пар символов, 10 из которых являются дубликатами. Как правильно их удалить? В других языках одним из способов решения этой проблемы является введение побочного эффекта путем создания структуры данных и вставки каждого элемента в структуру, но только в том случае, если его еще нет.

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

Edit: Я добавил определение своей функции «не одно и то же», которое использует имя (символ) и создает списки пар. 

(define (non-same name alist)
  (cond
    [(empty? alist) empty]
       [(equal? name (first (first alist))) (cons (first alist) (non-same name (rest     alist)))]
       [else (non-same name (rest alist))]))

Следующий тест проходит: 

(non-same 'Mary (pair 'Mary '(Jane Laura Dana Louise)))
;; outputs (list (list 'Mary 'Jane) (list 'Mary 'Laura) (list 'Mary 'Dana) (list 'Mary 'Louise))

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

Спасибо всем, кто прочитал этот вопрос, и особенно Крису за его полезные комментарии.

1 Ответ

0 голосов
/ 29 декабря 2010

После прочтения вопроса у меня возникло ощущение, что вы лаете не на то дерево.

Вам нужны только три функции: random-pick, non-same и arrangements. Последнее уже определено в упражнении 12.4.2.

Я полагаю из вашего вопроса, что вы хотите реализовать non-same. Вы захотите реализовать функцию, которую вы передадите в filter (или каков бы ни был эквивалент HtDP). Тогда это так просто, как: 

(define (non-same names arrangements)
  (define (usable? arrangement)
    ...)
  (filter usable? arrangements))

(Заполните, конечно, .... Эта функция должна только возвращать логическое значение, и вам не нужно вообще нажимать append (как вы делали в своем вопросе).)

Надеюсь, хватит намека. Если вам нужен еще один совет, просто спросите. : -)

...