Function: dash--next-lex-perm

dash--next-lex-perm is a byte-compiled function defined in dash.el.

Signature

(dash--next-lex-perm ARRAY N)

Documentation

Update ARRAY of N numbers with its next lexicographic permutation.

Return nil if there is no such successor. N should be nonzero.

This implements the salient steps of Algorithm L (Lexicographic permutation generation) as described in DE Knuth's The Art of Computer Programming, Volume 4A / Combinatorial Algorithms, Part I, Addison-Wesley, 2011, § 7.2.1.2, p. 319.

Source Code

;; Defined in ~/.emacs.d/elpa/dash-20260221.1346/dash.el
(defun dash--next-lex-perm (array n)
  "Update ARRAY of N numbers with its next lexicographic permutation.
Return nil if there is no such successor.  N should be nonzero.

This implements the salient steps of Algorithm L (Lexicographic
permutation generation) as described in DE Knuth's The Art of
Computer Programming, Volume 4A / Combinatorial Algorithms,
Part I, Addison-Wesley, 2011, § 7.2.1.2, p. 319."
  (setq n (1- n))
  (let* ((l n)
         (j (1- n))
         (al (aref array n))
         (aj al))
    ;; L2. [Find j].
    ;; Decrement j until a[j] < a[j+1].
    (while (and (<= 0 j)
                (<= aj (setq aj (aref array j))))
      (setq j (1- j)))
    ;; Terminate algorithm if j not found.
    (when (>= j 0)
      ;; L3. [Increase a[j]].
      ;; Decrement l until a[j] < a[l].
      (while (>= aj al)
        (setq l (1- l) al (aref array l)))
      ;; Swap a[j] and a[l].
      (aset array j al)
      (aset array l aj)
      ;; L4. [Reverse a[j+1]...a[n]].
      (setq l n)
      (while (< (setq j (1+ j)) l)
        (setq aj (aref array j))
        (aset array j (aref array l))
        (aset array l aj)
        (setq l (1- l)))
      array)))