Нахождение самого длинного подсписка в списке списков (Racket / Scheme) - PullRequest
Новая
       7

Нахождение самого длинного подсписка в списке списков (Racket / Scheme)

2 голосов
/ 06 апреля 2020

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

(define longest '())
;returns longest sublist in a list of lists
(define (longestSub losl)
  (set! longest (car losl))
   (for ([x (- (length losl) 1)])
    (if (>= (length (list-ref losl x)) (length longest))
        (set! longest (list-ref losl x))
        (void losl)))
  (display longest))

Например, если «losl» равен ((1 2) (3 4 5) (6 7 8)), я хочу, чтобы оно вернулось (6 7 8), но сейчас это будет возврат (3 4 5). Может кто-нибудь сказать мне, что я делаю не так?

Ответы [ 2 ]

3 голосов
/ 06 апреля 2020

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

С (for ([x (- (length losl) 1)]) ;... l oop не повторяется до конца ввода список. С заданным значением (length losl) равно 3; поэтому предложение l oop эквивалентно (for ([x 2]) ;..., что аналогично (for ([x (in-range 2)]) ;.... Это генерирует значения 0 и 1 для x, но 2 никогда не достигается, поэтому последний список никогда не проверяется. Чтобы исправить эту проблему, измените на: 

(define (longestSub losl)
  (set! longest (car losl))
  (for ([x (length losl)])
    (if (>= (length (list-ref losl x)) (length longest))
        (set! longest (list-ref losl x))
        (void losl)))
  (display longest))

Кстати, вы можете избавиться от (void losl), используя when вместо if: 

(define (longestSub losl)
  (set! longest (car losl))
  (for ([x (length losl)])
    (when (>= (length (list-ref losl x)) (length longest))
      (set! longest (list-ref losl x))))
  (display longest))

Используя все oop и set! для этого, возможно, не самое идиоматическое c решение. Другой подход заключается в использовании рекурсии и вспомогательной функции, которая передает текущий самый длинный подсписок: 

(define (longest-sublist losl)
  (define (lsl-helper losl longest)
    (cond [(empty? losl)
           longest]
          [(>= (length (first losl)) (length longest))
           (lsl-helper (rest losl) (first losl))]
          [else (lsl-helper (rest losl) longest)]))
  (lsl-helper losl '()))

Оба решения будут работать, но есть пара отличий. Решение OP потерпит неудачу с ошибкой времени выполнения в случае пустого списка для ввода: (longestSub '()). Но это рекурсивное решение будет возвращать пустой список для того же ввода вместо сбоя. Какое поведение предпочтительнее, зависит от ОП. Другое отличие состоит в том, что это рекурсивное решение возвращает самый длинный подсписок, а OP-решение просто печатает его.

2 голосов
/ 06 апреля 2020

Выбиваем меньший элемент или левый элемент. 

(define (longest  lst)
  (foldr (λ (a b) (if (> (length a) (length b)) a b))
         '()
         lst))

;;; TEST
(longest '((1 2) (3 4 5) (6 7 8)))
...