Самая длинная цепочка элементов в Лиспе - PullRequest
Новая
       3

Самая длинная цепочка элементов в Лиспе

2 голосов
/ 25 марта 2020

Заявление: найти самую длинную цепочку символов и вернуть ее. Пример: вход: '(1 2 2 3 3 3 4 4 4 4 5 6 ) выход: '(4 4 4 4)

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

код: 

(define finalL (list))
(define (sameNum liste) 
  (if (or (null? liste) (null? (cdr liste)))
      ;; true
      '()
      ;; false
      (let ([lcdr (sameNum (cdr liste))]) 
        (if (eqv? (car liste) (car(cdr liste)) )
            ;; true
            (if (= (length liste) 2)
                ;; true
                (cons (car liste) (cons (car(cdr liste)) lcdr)) 
                ;; false
                (if (or (not(eqv? (car(cdr liste)) (car(cdr (cdr liste))) )) (null? (cdr liste)) )
                    (cons (car liste) (cons (car(cdr liste)) lcdr)) ;true
                    (cons (car liste) lcdr))) ; false
             ;; false
            (if (let ((x (length lcdr)) (y (length finalL))) (< x y))
                ;; true
                (crushL finalL lcdr)
                ;; false
                finalL)))))
;; crush L1 and replace by value of L2
(define (crushL L1 L2)
  (if (null? L1)
      ;; true
      (cons L2 L1)
      ;; false
      (crushL (cdr L1) L2)))

1 Ответ

2 голосов
/ 25 марта 2020

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

  • текущую цепочку (примечание: вы можете построить их в обратном направлении, поскольку все элементы одинаковы!);
  • как долго это будет;
  • самая длинная цепь, которую вы видели;
  • как долго это было.

Тогда вы принимаете решения на основе того, является ли элемент, на который вы смотрите, тем же самым, что и первый элемент в текущей цепочке (все еще строит ту же цепочку) или нет (начиная новую цепочку), и, если вы все еще строите ту же цепочку, эта цепочка теперь самая длинная.

Например: 

(define (longest-chain l)
  (let lc-loop ([tail l]
                [current-length 0]
                [current-chain '()]
                [longest-length 0]
                [longest-chain '()])
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)])))

Для дополнительных точек: если имеется более одной самой длинной цепочки, какую из них возвращает эта функция? Как ты мог изменить это, чтобы он сделал другой выбор? Или даже выбор random !

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

(define (longest-chain l)
  (define (lc-loop tail
                   current-length current-chain
                   longest-length longest-chain)
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)]))
  (lc-loop l 0 '() 0 '()))

Это полностью эквивалентно вышеприведенной версии. Если вас не устраивают внутренние define s, тогда вы можете превратить lc-loop в определение верхнего уровня.

...