August 19, 2024
P30 - Sorting a list of lists according to length of sublists
a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.
Example:* (lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L))
b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency; i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.
Example:* (lfsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))((I J K L) (O) (A B C) (F G H) (D E) (D E) (M N))
Note that in the above example, the first two lists in the result have length 4 and 1, both lengths appear just once. The third and forth list have length 3 which appears twice (there are two list of this length). And finally, the last three lists have length 2. This is the most frequent length.
lisp
;;; Returns a list ordered according to the size of the sublists;;;
(defun lsort (origlist)
(sort orig-list #'> :key #'length))
;;; Returns a new list, with elements of the form (N ELEM), where ;;;
;;; N is the frequency of the list size ELEM and ELEM is a sublist ;;;
;;; original. ;;
(defun lfmark (rest-list &optional (orig-list rest-list))
(if (eql rest-list nil)
nil
(cons (list (lfreq orig-list (length (car rest-list))) (car rest-list)) (lfmark (cdr rest-list) orig-list))
;;; receives a list with elements of the form (ELEMENT KEY) and returns a new ;;;
;;; list without the keys ELEM ;;;
(defun lfunmark (origlist)
(if (eql orig-list nil)
nil
(cons (second (car orig-list)) (lfunmark (cdr orig-list)))
;;; counts the number of lists with size e-length in the orig-list ;;;
(defun lfreq (orig-list e-length)
(if (eql orig-list nil)
0
(if (eql (length (car orig-list)) e-length)
(+ (lfreq (cdr orig-list) e-length) 1)
(lfreq (cdr orig-list) e-length))
;;; returns a list ordered by the frequency of its sublists;;;
(defun lfsort (orig-list)
(let ((marked-list (lfmark orig-list))
(lfunmark (sort marked-list #'> :key #'(lambda (x) (car x)))))