Разделение списка a-списков на подсписки - PullRequest
Новая
       0

Разделение списка a-списков на подсписки

0 голосов
/ 13 февраля 2019

Для хобби-проекта я имею дело со списками a-списков, таких как

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

, где список может содержать до девяти элементов, а a-списки состоят только из целых чисел из0 до 9.Я хочу разбить список на подузлы с последовательными cdr с.

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

Использование iterate Я предложил двухэтапный подход.Во-первых, отсканируйте список и проверьте, есть ли подразделения или нет, возвращая позиции промежутков.А во-вторых, разделите список на части с помощью функции 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 в одну?Есть ли разница в стиле или эффективности?

1 Ответ

0 голосов
/ 13 февраля 2019

Я думаю, что проблему можно решить, выполнив итерации следующим образом: собрать все элементы в списке, пока их 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)
...