Pastable version of Lexicographically next permutation

<pre class='prettyprint' language='lisp'>; 5*O(n)
  (defun next-lex (a)
    (let* ((r (reverse a))
           (pivot (first-down r)))
      (multiple-value-bind
        (less-pivot greater-pivot before-pivot) (partition-upto pivot r)
        (nreverse (append (cdr greater-pivot) (list pivot) less-pivot
              (list (car greater-pivot)) before-pivot)))))

; O(n)
  (defun first-down (a)
    (if (numberp (cadr a))
      (if (&gt; (car a) (cadr a))
        (cadr a)
        (first-down (cdr a)))
      nil))

; O(n)
  (defun partition-upto (pivot a)
    (labels ((partition-sub (pivot a less more)
      (cond
        ((eql (car a) pivot)
         (values less (nreverse more) (cdr a)))
        ((&gt; (car a) pivot)
         (partition-sub pivot (cdr a) less (cons (car a) more)))
        ((&lt; (car a) pivot)
         (partition-sub pivot (cdr a) (cons (car a) less) more)))))
      (partition-sub pivot a () ())))

;; &gt; (next-lex '(1 3 5))
;; (1 5 3)</pre>
<a href="http://www.refactormycode.com/codes/55-lexicographically-next-permutation" style="color:#fff" title="As seen on RefactorMyCode.com"><img alt="Small_logo" src="http://www.refactormycode.com/images/small_logo.gif" style="border:0" /></a>

Refactor :my => 'code'

Recent

Popular

Pastable version of Lexicographically next permutation