Jump to content

lisp / special divide - help needed


Recommended Posts

LISP...
any solution? i want to DIVIDE a seq into sublists -> when it's asc into a list, "rest"  into single-listed values - thanx a lot for some help 🙂

 

;;; input
(divide* '(14 12 3 13 15 8 4 10 17 2 16 0 1 6 7 5 11 9))

;;; output
=> ((14) (12) (3 13 15) (8) (4 10 17) (2 16) (0 1 6 7) (5 11) (9))

 

Link to post
Share on other sites

For a generic solution, you could use some function split-if that expects a Boolean function as argument comparing two consecutive pairs, and always splits a sublist if the Boolean function returns True. I don't have such a Lisp function at hand right now, but of an algorithm idea here is a similar Python function, only that this expects a Boolean function of a single argument only. If you port this function to Lisp, you could then generalise it by checking the number of arguments the given Boolean function expects, and it apply it always to the corresponding consecutive number of elements of xs.

 

def split_if(fun, xs):
    """
    Splits `xs` (list) into sublists based on a test. Starts a new sublist
    at every element for which Boolean function `fun` returns true.

    Examples
    --------

    >>> split_if(lambda x: x % 3 == 0, [0, 1, 2, 3, 4, 5])
    [[0, 1, 2], [3, 4, 5]]

    >>> split_if(lambda x: x % 3 == 0, [1, 2, 3, 4, 5, 6, 7])
    [[1, 2], [3, 4, 5], [6, 7]]

    NOTE:
    Internally, `split_if` skips the first element of `xs`. So, if `fun` is
    stateful, it should initialise its state using that first element.
    For an example, see implementation of `format_api.split_into_sections`.
    """
    result_list = []
    start = 0
    # Collect new list up to x whenever fun(x) == true, but not before first element
    for index, x in enumerate(xs[1:]):
        if fun(x):
            result_list.append(xs[start:index+1])
            start = index+1
    if start == 0:
        return [xs]
    result_list.append(xs[start:])
    return result_list

 

 

Here is another approach as well with a Lisp function from my toolbox expecting a list of positions where to split the list. You could find those positions by iterating over conservative pairs of your list elements with the function positions-if listed below.

 

OK, none of this is a ready made solution, but all the necessary pieces are there 🙂  I need to head back to work now ....

 

Torsten

 

(defun subseqs (sequence positions &optional end)
  "Splits `sequence' into a list of subsequences split at `positions'. Each element in `positions' specifies a position at which a new sublist starts.

; (subseqs '(0 1 2 3 4 5 6) '(0 2 4))
=> ((0 1) (2 3) (4 5 6))

; (subseqs '(0 1 2 3 4 5 6) '(2 4 6) 5)
=> ((2 3) (4))

`positions' are implicitly sorted and positions beyond end are excluded.
"
  (let* ((updated-pos (sort (if end
			       (remove-if #'(lambda (x) (>= x end))
					  positions)
			       positions)
			    #'<))
	(full-pos (append updated-pos
			  (list (if end
				    end
				    (length sequence))))))
    (mapcar #'(lambda (start end)
		(subseq sequence start end))
	    (butlast full-pos)
	    (rest full-pos))
    ))
    
   
(defun positions-if (predicate sequence &key key (start 0))
  "Like the Common Lisp function `position-if', but returns all positions in `sequence' that match `predicate'.

; (positions-if #'oddp '((1) (2) (3) (4)) :key #'car)
; => (0 2)"
  (labels ((aux (predicate sequence &key key (start 0) accum)
	     (let ((pos (position-if predicate sequence :start start :key key)))
	       (if pos
		   (aux predicate sequence :start (1+ pos) :key key :accum (cons pos accum))
		   (reverse accum)))))
    (aux predicate sequence :start start :key key)))

#|
;; comparison
(position-if #'oddp '((1) (2) (3) (4)) :key #'car)
|#

      

 

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Ă—
Ă—
  • Create New...

Important Information

Terms of Use Privacy Policy