Lisp中最长的元素链

语句：找出最长的字符链并返回。 例如：输入：'(1 2 2 3 3 3 4 4 4 4 5 6 )输出：'(4 4 4 4)

问题：我可以设法识别列表中的所有不同组并比较它们，但无法让函数返回正确的子集列表。它仅返回最后分析的组。

code:

(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)))

诀窍是在你浏览清单时保留四件事：

• 当前链（注意：您可以向后构建这些链，因为所有元素都是相同的！）；
• 有多长？
• 你见过的最长的链条；
• 多久that was.

然后，您根据正在查看的元素是否与当前链中的第一个元素相同（仍在构建相同的链）或不同（开始新的链）做出决定，如果您仍在构建相同的链，该链现在是否是最长的。

像这样：

(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 choice!

注意上面版本的函数使用named let，这是Scheme 中的标准构造。如果你不想使用它，你可以将它变成一个显式函数：

(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 '()))

这与上面的版本完全等效。如果您对内部不满意defines，然后你可以转动lc-loop进入顶级定义。