Place k elements such that minimum distance is maximized — binary search approach

explained and implemented declaratively with Common Lisp

We are starting off from the Efficient Solution published here:, basically just reimplementing it.
→ https://www.geeksforgeeks.org/place-k-elements-such-that-minimum-distance-is-maximized/
Open it in another tab as there will be references made to it in the below text.

Given an array representing n positions along a straight line. Find k (where k ≤ n) elements from the array such that the minimum distance between any two (consecutive points among the k points) is maximized.

For a reason that maybe the original may need to explain, we process the input sorted and such will be exhibited in below examples. The original has its implementations start with a call to a sorting subroutine.

Examples:

{1, 2, 4, 8, 9}, k = 3
3 elements: {1, 4, 8},
Resulting in a minimum distance of 3
{1, 2, 5, 7, 11, 12}, k = 3
3 elements: {1, 7, 12},
resulting in a minimum distance of 5 (between 7 and 12)

isFeasible

Consider the isFeasible function from the GeeksForGeeks' Radhav Jajodia's original. It is not too clear immediately to most and requires a different approach to explaining it than the original.

It accepts arguments:

Going through the sorted numbers from start to end, it counts (starting with the first one) the ones that are at least mid distance away from the previously counted one. When the count reaches k, it returns true. If it never does, it returns false.

Going through the sorted numbers from start to end, it counts them omitting the ones that were within <mid distance from the previously counted one (less than mid units away from it). When the count reaches k, it returns true. If it never does, it returns false.

The binary search

The function is utilized by the main algorithm in the following manner: a binary search over possible minimum distances is performed, with the boundaries being: 1 (lower boundary) and the upper boundary being… the value of the greatest number.

I believe that is incorrect as suboptimal and the correct upper boundary should be at most the distance (i.e. difference) before the least and the greatest element. We could also further narrow that down to maybe that distance divided by k, for an arithmetic average.

The original is explaining why is the lower boundary one:

left is initialized with 1 and not with arr[0] because, minimum distance between each element can be one and not arr[0]. consider this example:
 arr[] = {9,12} and you have to place 2 element then left = arr[0] will force the function to look the answer between range arr[0] to arr[n-1], i.e 9 to 12, but the answer is 3 so It is required that you initialize the left with 1.

Each check of the binary search is made at the integer arithmetic average (assigned to mid) of the current set lower and upper boundaries (i.e. integer division-by-two of the sum of them two, which means floored in case of positive numbers), starting with the aforementioned initial ones. A check is a call to isFeasible —

The checks stop when the boundaries will become equal or nonsense (lower greater than the upper), and the last mid that isFeasible returned true for is returned.

Indulging in clarifying the final loop iteration of the binary search

Let's consider the check previous to the end condition being reached. In case of {1 2 3 4}, we get the average 2 and we can get either a 2+1=3 and a {3 4}, or a 2 and a {1 2}. With {1 2 3 4 5}, we get 3 and thus either 3+1=4 and {4 5} or 3 and {1 2 3}. From our acquaintance with the properties of arithmetic average we know that these ranges can be transposed by any positive offset for these findings of ours to hold true. It becomes apparent that it must be either {1 2 3} or {1 2}.

We thus found that the boundaries, if we didn't err, never become nonsense, and the loop end condition could be (albeit less safely for the case we now erred) considered to be equality.

A declarative approach to isFeasible

Let's have a function that returns an array of all the distances between elements, in order.

(defun just-distances (arr)
  (if (null (cdr arr)) nil
      (cons (- (cadr arr) (car arr))
            (just-distances (cdr arr)))))

CL-USER> (just-distances '(1 2 5 7 11 12))
(1 3 2 4 1)
CL-USER> (just-distances '(1 2 4 8 9))
(1 2 4 1)

We want to look at the distances that are at least mid. Going over the not-far-enough can be otherwise interpreted as summing distances. Let's write a function that will sum the adjoining distances.

(defun remove-too-close (mid arr)
  (if (null arr) nil
      (let ((our (car arr))
	    (rest (cdr arr)))
	(if (<= mid our)
	    (cons our
		  (remove-too-close mid rest))
	    (if (null rest) nil
		(remove-too-close
		 mid
		 (cons (+ our (car rest))
		       (cdr rest))))))))
 
CL-USER> (remove-too-close 1 (just-distances '(1 2 5 7 11 12)))
(1 3 2 4 1)
CL-USER> (remove-too-close 2 (just-distances '(1 2 5 7 11 12)))
(4 2 4)
CL-USER> (remove-too-close 3 (just-distances '(1 2 5 7 11 12)))
(4 6)
CL-USER> (remove-too-close 4 (just-distances '(1 2 5 7 11 12)))
(4 6)
CL-USER> (remove-too-close 5 (just-distances '(1 2 5 7 11 12)))
(6 5)
CL-USER> (remove-too-close 6 (just-distances '(1 2 5 7 11 12)))
(6)

We can see that the number of distances ("edges") is one less than the number of our "nodes". We can thus see that

given mid
 best k
1
 6
2
 4
3
 3
4
 3
5
 3
6
 2

The distances could be replaced with a data structure (distance . (left . right)) along with a summing function to replace + : (cons (+ (car a) (car b)) (cons (cadr a) (cddr b))). But that's more useful for maybe debugging, as it makes the code a bit more bloated and for practical purposes the elements can be recovered by taking the leftmost element and adding the distances to it.

The equivalent of the function isFeasible would be taking the result of remove-too-close and see if its length is greater or equal to k-1.

The need for lazy sequences: to get rid of checking and summing beyond k elements

What the above code needlessly does is calculating the distances and summing them beyond when k elements got already found. This is because we used eagerly evaluated lists of Common Lisp. We need to introduce laziness. While Common Lisp seems to have more recent standards introducing language constructs for lazy sequences, the most plain usual way to achieve laziness in sequences in Common Lisp has been having zero-argument lambdas as CDR.

So instead of (first . rest) it is now going to be (first . (lambda () rest)).

before
 after
 
(defun just-distances (arr)
  (if (null (cdr arr)) nil

      (cons (- (cadr arr)
               (car arr))
            (just-distances
             (cdr arr)))))

(defun just-distances (arr)
  (if (null (cdr arr)) nil
      (lambda ()
	(cons (- (cadr arr)
	         (car arr))
	      (just-distances
	       (cdr arr))))))
 

(defun funcall? (x)
  (if (null x) nil (funcall x)))
 
(defun remove-too-close (mid arr)
  (if (null arr) nil
      (let ((our (car arr))
	    (rest (cdr arr)))
	(if (<= mid our)
	    (cons our

		  (remove-too-close
		   mid rest))
	    (if (null rest) nil
		(remove-too-close
		 mid
		 (cons
		  (+ our (car rest))
		  (cdr rest))))))))
 
(defun remove-too-close (mid arr)
  (if (null arr) nil
      (let ((our (car arr))
	    (rest (cdr arr)))
	(if (<= mid our)
	    (cons our
		  (lambda
		   () (remove-too-close
		       mid (funcall? rest))))
	    (if (null rest) nil
		(remove-too-close
		 mid
		 (let ((rest (funcall rest)))
		   (cons (+ our (car rest))
			 (cdr rest)))))))))

 
(defun unlazy (arr)
  (cons (car arr)
	(if (null (cdr arr)) nil
	    (unlazy (funcall (cdr arr))))))
A function evaluating the whole such lazy sequence into a regular list

The final part: to wrap it all up in neat declaratively-done binary search in Lisp

There is no need to do that for the sake of explaining alone. I want to do that, but maybe not right now… I spent way too much time writing this article and I need to do other stuff rn.