Exercise 4.50.  Implement a new special form ramb that is like amb 
except that it searches alternatives in a random order, rather than from 
left to right. Show how this can help with Alyssa's problem in exercise 
4.49.

————————————————————————————————————————————————————————————————————————

;; from the book we have:

(define (analyze-amb exp)
  (let ((cprocs (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) env
                           succeed
                           (lambda ()
                             (try-next (cdr choices))))))
      (try-next cprocs))))

;; analyze-ramb is very similar, but we re-order the choices randomly 
;; each time the expression is evaluated (not just once when it is 
;; analyzed)

(define (analyze-ramb exp)
  (let ((cprocs (map analyze (ramb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) env
                           succeed
                           (lambda ()
                             (try-next (cdr choices))))))
      (try-next (random-permutation-of cprocs)))))

; this is O(n²), and I'm sure this can be improved, but in most programs n will be quite small anyway
(define (random-permutation-of items)
  (define (permute items length)
    (if (= 0 length)
        '()
        (let ((selected-index (random length)))
          (let ((bubbled (bubble items selected-index)))
            (cons (car bubbled) (permute (cdr bubbled) (- length 1)))))))
  (permute items (length items)))

; move the index'th item to the front of the list, leaving the rest of the items in some unspecified order
(define (bubble items index)
  (if (= 0 index)
      items
      (let ((rest (bubble (cdr items) (- index 1))))
        (cons (car rest) (cons (car items) (cdr rest))))))