时间戳

首页 > 解决方案 > 将 a-list 列表拆分为子列表

list - 将 a-list 列表拆分为子列表

问题描述

对于一个爱好项目，我处理一个列表，比如

((0 . 0) (0 . 1) (0 . 3) (0 . 4) (0 . 7) (0 . 8))

其中列表最多可以有九个元素，并且 a-lists 仅包含从0to的整数9。我想将列表拆分为具有连续cdrs 的子单元。

(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))

一个子单元可以只有一个元素，列表可以没有子单元，例如：

((0 . 0) (0 . 1) (0 . 2) (0 . 4))或者 ((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4))

结果应该是：

(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))

(((0 . 0) (0 . 1) (0 . 2)) ((0 . 4)))

(((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4)))

使用迭代我想出了一个两步的方法。首先，扫描列表并检查是否有子单元，返回间隙的位置。其次，使用我之前实现的函数拆分列表split-at：

(defun split-at (count original-list)
  (unless (or (null original-list) (minusp count)
              (>= count (length original-list)))
    (list (subseq original-list 0 count)
          (subseq original-list count))))

(defun sub-units (units)
  "Scan UNITS for sub-units."
  (iter
    (for (a . b) in units)
    (for last-b previous b initially -1)
    (for pos from 0)
    (unless (= 1 (- b last-b))
      (collecting pos))))

(defun split-sub-units (units)
  "Splits UNITS into its sub-units."
  (iter
    (with pos = (or (sub-units units) (list 0)))
    (for p in pos)
    (for last-p previous p)
    (for (head tail) first (split-at p units) then (split-at last-p tail))
    (when head
      (collect head into result))
    (finally (return (nconc result (list tail))))))

是否可以将这两个功能合并sub-units为split-sub-units一个？它对风格或效率有什么影响吗？

标签： listcommon-lisp

解决方案

我认为可以通过以下方式迭代来解决问题：收集一个列表中的所有元素，直到它们的cdr连续，然后重复前面的过程，直到原始列表为空，收集所有生成的列表。这可以迭代地完成，总成本为O(n)，其中n是原始列表的长度。

我使用loop而不是iterate因为我更熟悉第一个构造，将它转换为迭代应该很简单。

(defun split (l)
  (loop for (a b) = (loop for (x . y) on l
                          collect x into a
                          when (and y (/= (cdar y) (1+ (cdr x))))
                            do (return (list a y))   ; split here
                          finally (return (list a nil))) ; never split
        collect a        ; a list has been produced, collect it
        while b          ; if there are other elements
        do (setf l b)))  ; repeat splitting over them

几个测试：

CL-USER> (split '((0 . 0) (0 . 1) (0 . 2)))
(((0 . 0) (0 . 1) (0 . 2)))
CL-USER> (split '((0 . 0) (0 . 1) (0 . 3) (0 . 4) (0 . 7) (0 . 8)))
(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))
CL-USER> (split '((0 . 0)))
(((0 . 0)))
CL-USER> (split '())
(NIL)

推荐阅读