sc/permutations [ Modules ]

[ Top ] [ Modules ]

NAME

 permutations

 File:             permutations.lsp

 Class Hierarchy:  none, no classes defined.

 Version:          1.1.0

 Project:          slippery chicken (algorithmic composition)

 Purpose:          Various permutation functions.

 Author:           Michael Edwards: m@michael-edwards.org

 Creation date:    10th November 2002

 $$ Last modified:  15:32:50 Sat Mar 16 2024 CET

 SVN ID: $Id$

permutations/avoid-common-elements [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DATE

 December 6th 2019, Heidhausen

DESCRIPTION

 Taking a list of sublists, move the sublists around to try and avoid
 consecutive sublists having common elements. Note that even if it's not
 possible to completely solve this problem, a re-ordered list will be
 returned along with a warning detailing where things were no longer
 possible. No further, more complex attempts are made at that point. NB In
 that case shuffling before calling this function might help

ARGUMENTS

 - the list of sublists (of any element type)

OPTIONAL ARGUMENTS

 keyword arguments:
 - :test. The function to be passed to (intersection) for testing equivalence
   amongst list elements. Default = #'eq
 - :accept. The number of common elements to accept amongst sublists. Default
   = 0
 - :warn. Issue a warning if we can't complete? Default = T
 - :all-on-fail. Return the unprocessed (failing) elements if we can't
   complete? If NIL then we'll return less sublists than given but there will
   be no common elements, at least. Default = T.

RETURN VALUE

 a list: the first argument with re-ordered sublists.

EXAMPLE

(avoid-common-elements
 '((1 2 3) (4 5 6) (5 4 6) (4 6 1) (2 3 4) (2 3 1) (1 3 2)))
-->
WARNING: permutations::avoid-common-elements: did 4 but can't complete. 
Current: (1 3 2)
Rest: ((4 6 1) (2 3 4))
((1 2 3) (4 5 6) (2 3 1) (5 4 6) (1 3 2) (4 6 1) (2 3 4))

(avoid-common-elements
 '((1 2 3) (4 5 6) (5 4 6) (3 2 1) (2 3 1) (6 5 4) (3 1 2)))
-->
((1 2 3) (4 5 6) (3 2 1) (5 4 6) (2 3 1) (6 5 4) (3 1 2))

SYNOPSIS

(defun avoid-common-elements (lists &key (test #'eq) (accept 0) (warn t)
                                      (all-on-fail t))

permutations/inefficient-permutations [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Return a shuffled, non-systematic list of all possible permutations of a  
 set of consecutive integers beginning with zero. 

 The function's first argument, <level>, is an integer that determines how
 many consecutive integers from 0 are to be used for the process. An
 optional keyword argument <max> allows the user to specify the maximum
 number of permutations to return. 

 This function differs from the "permutations" function in that it's result
 is not ordered systematically. 

 The function simply returns a list of <max> permutations of the numbers
 less than <level>; it does not permutate a given list.   

 The function is inefficient in so far as it simply shuffles the numbers and
 so always has to check whether the new list already contains the shuffled
 before storing it. 
 
 The order of the permutations returned will always be the same unless <fix>
 is set to NIL. 

 Keyword argument <skip> allows the user to skip a number of permutations,
 which is only sensible if :fix is set to T. 

ARGUMENTS

 An integer that indicates how many consecutive integers from 0 are to be
 used for the process. 

OPTIONAL ARGUMENTS

 keyword arguments:
 - :max. An integer that indicates the maximum number of permutations to be
   returned.
 - :skip. An integer that indicates a number of permutations to skip.
 - :fix. T or NIL to indicate whether the given sequence should always be
   shuffled with the same (fixed) random seed (thus always producing the
   same result). T = fixed seed. Default = T.
 - :if-not-enough. A function object (or NIL) to call when :max was
   requested but we can't return that many results.  Default = #'error. 

RETURN VALUE

 A list.

EXAMPLE

;; Creating a shuffled, non-systematic list of all permutations of consecutive
;; integers 0 to 4 
(inefficient-permutations 4)

=> ((2 3 0 1) (3 1 2 0) (2 0 3 1) (1 0 2 3) (1 2 3 0) (0 2 3 1) (2 1 0 3)
    (0 1 2 3) (2 3 1 0) (1 2 0 3) (3 0 1 2) (3 1 0 2) (1 3 2 0) (1 0 3 2)
    (2 0 1 3) (3 2 1 0) (2 1 3 0) (3 2 0 1) (1 3 0 2) (0 2 1 3) (3 0 2 1)
    (0 1 3 2) (0 3 2 1) (0 3 1 2))

;; Using 0 to 4 again, but limiting the number of results returned to a maximum
;; of 7
(inefficient-permutations 4 :max 7)

=> ((2 3 0 1) (3 1 2 0) (2 0 3 1) (1 0 2 3) (1 2 3 0) (0 2 3 1) (2 1 0 3))

;; The same call will return the same "random" results each time by default
(loop repeat 4 do (print (inefficient-permutations 3 :max 5)))

=>
((2 0 1) (2 1 0) (0 2 1) (1 0 2) (1 2 0)) 
((2 0 1) (2 1 0) (0 2 1) (1 0 2) (1 2 0)) 
((2 0 1) (2 1 0) (0 2 1) (1 0 2) (1 2 0)) 
((2 0 1) (2 1 0) (0 2 1) (1 0 2) (1 2 0))

;; Setting the :fix argument to NIL will result in different returns
(loop repeat 4 do (print (inefficient-permutations 3 :max 5 :fix nil)))

=>
((1 0 2) (0 1 2) (1 2 0) (2 1 0) (0 2 1)) 
((1 2 0) (2 0 1) (2 1 0) (1 0 2) (0 1 2)) 
((0 1 2) (1 0 2) (2 0 1) (1 2 0) (2 1 0)) 
((0 2 1) (1 2 0) (0 1 2) (2 0 1) (1 0 2))

SYNOPSIS

(defun inefficient-permutations (level &key (max nil) (skip 0) (fix t)
                                         (if-not-enough #'error))

permutations/inefficiently-permutate [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Return a shuffled, non-systematically ordered list of all possible
 permutations of an original list of elements of any type. An optional
 keyword argument <max> allows the user to specify the maximum number of
 permutations to return.

 As opposed to the function "permutate", inefficiently-permutate returns the
 elements of the specified <list> as a flat list, unless the keyword
 argument <sublists> is set to T, whereupon the function returns the result
 as a list of lists, each one being a permutation of <list>.

 The function is inefficient in so far as it simply shuffles the numbers and
 so always has to check whether the new list already contains the shuffled
 sublist before storing it.
 
 The order of the permutations returned will always be the same unless <fix>
 is set to NIL. 

ARGUMENTS

 - A list.

OPTIONAL ARGUMENTS

 keyword arguments:
 - :max. An integer that indicates the maximum number of permutations to be
   returned.
 - :skip. An integer that indicates a number of permutations to skip.
 - :fix. T or NIL to indicate whether the given sequence should always be
   shuffled with the same (fixed) random seed (thus always producing the
   same result). T = fixed seed. Default = T.
 - :sublists. T or NIL to indicate whether the returned result should be
   flattened into a one-dimensional list or should be left as a list of
   lists. T = leave as list of lists. Default = NIL.
 - :clone. T or NIL to indicate whether objects in the list should be cloned
   as they are permutated (so that they are unique objects rather than
   shared data space).  Useful perhaps if e.g. you're cloning chords which
   will then have their own marks. etc.  If T then the list must contain
   slippery-chicken named-objects or types subclassed from them (as is every
   slippery-chicken class).
 - :if-not-enough. A function object (or NIL) to call when :max was
   requested but we can't return that many results.  Default = #'error. 

RETURN VALUE

 A list.

EXAMPLE

;; By default the function returns a flattened list of all possible
;; permutations in a shuffled (random) order
(inefficiently-permutate '(a b c))

=> (C A B C B A A C B B A C B C A A B C)

;; The length of the list returned can be potentially shortened using the :max
;; keyword argument. Note here that the value given here refers to the number
;; of permutations before the list is flattened, not to the number of
;; individual items in the flattened list.
(inefficiently-permutate '(a b c) :max 3)

=> (C A B C B A A C B) 

;; By default the function is set to using a fixed random seed, causing it to
;; return the same result each time
(loop repeat 4 do (print (inefficiently-permutate '(a b c))))

=>
(C A B C B A A C B B A C B C A A B C) 
(C A B C B A A C B B A C B C A A B C) 
(C A B C B A A C B B A C B C A A B C) 
(C A B C B A A C B B A C B C A A B C) 

;; Setting the :fix keyword argument to NIL allows the function to produce
;; different output each time
(loop repeat 4 do (print (inefficiently-permutate '(a b c) :fix nil)))

=>
(B A C A C B B C A A B C C B A C A B) 
(A C B B A C C B A C A B B C A A B C) 
(A C B B A C B C A A B C C A B C B A) 
(B A C A B C C A B C B A B C A A C B) 

;; Setting the :sublists keyword argument to T causes the function to return a
;; list of lists instead
(inefficiently-permutate '(a b c) :sublists t)

=> ((C A B) (C B A) (A C B) (B A C) (B C A) (A B C))

SYNOPSIS

(defun inefficiently-permutate (list &key (max nil) (skip 0) (fix t)
                                clone (sublists nil) (if-not-enough #'error))

permutations/move-repeats [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Move, when possible, any elements within a given list that are repeated
 consecutively.  

 When two consecutive elements repeat, such as the c in '(a b c c b a),
 the function moves the repeated element to the next place in the given
 list that won't produce a repetition. When no such place can be found in
 the remainder of the list, the offending element is moved to the end of the
 given list and a warning is printed.

 This function can be applied to simple lists and lists with sublists.
 However, due to this function being designed for--but not limited to--use
 with the results of permutations, if the list has sublists, then instead of
 repeating sublists being moved, the last element of a sublist is checked
 for repetition with the first element of the next sublist. See the first
 example below.

 NB: This function only moves elements further along the list; it won't place
     them earlier than their original position.  Thus:
     
     (move-repeats '(3 3 1)) 

     will return (3 1 3), while 

     (move-repeats '(1 3 3)) 

     will leave the list untouched and print a warning. 

ARGUMENTS

 - A list.

OPTIONAL ARGUMENTS

 - A function that serves as the comparison test. Default = #'eq. 

RETURN VALUE

 A list.

EXAMPLE

;;; Used with a list of lists.  Note that the repeating C, end of sublist 1,
;;; beginning of sublist 2, is moved, not the whole repeating sublist (c a b).
(move-repeats '((a b c) (c a b) (c a b) (d e f) (a b c) (g h i)))

=> ((A B C) (D E F) (C A B) (C A B) (A B C) (G H I))

;;; Works with simple lists too:
(move-repeats '(1 2 3 3 4 5 6 7 8 8 9 10))

=> (1 2 3 4 3 5 6 7 8 9 8 10)

;; Moves the offending element to the end of the list and prints a warning when
;; no solution can be found  
(move-repeats '((a b c d) (d c b a) (b c a d) (c a b d)))

=> ((A B C D) (B C A D) (C A B D) (D C B A))
WARNING:
   move-repeats: can't find non-repeating place! 
   present element: (D C B A), elements left: 1

SYNOPSIS

(defun move-repeats (list &key (warn t) (test #'eq))

permutations/multi-shuffle [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Applies the shuffle function a specified number of times to a specified
 list.  
 
 NB: As with the plain shuffle function, the order of the permutations
     returned will always be the same unless the keyword argument
     :fix is set to NIL.   

ARGUMENTS

 - A sequence.

OPTIONAL ARGUMENTS

 keyword arguments:
 - :start. A zero-based index integer indicating the first element of a
   subsequence to be shuffled. Default = 0.
 - :end. A zero-based index integer indicating the last element of a
   subsequence to be shuffled. Default = the length of the given sequence.
 - :copy. T or NIL to indicate whether the given sequence should be copied
   before it is modified or should be destructively shuffled. 
   T = copy. Default = T.
 - :fix. T or NIL to indicate whether the given sequence should always be
   shuffled with the same (fixed) random seed (thus always producing the
   same result). T = fixed seed. Default = T.
 - :reset. T or NIL to indicate whether the random state should be reset
   before the function is performed.  T = reset. Default = T.

RETURN VALUE

 - A sequence.

EXAMPLE

;; Simple multi-shuffle with default keywords.
(multi-shuffle '(a b c d e f g) 3)

=> (B A C E D G F)

;; Always returns the same result by default.
(loop repeat 4 do (print (multi-shuffle '(a b c d e f g) 3)))

=>
(B A C E D G F) 
(B A C E D G F) 
(B A C E D G F) 
(B A C E D G F)

;; Set keyword argument :fix to NIL to return different results each time 
(loop repeat 4 do (print (multi-shuffle '(a b c d e f g) 3 :fix nil)))

=>
(G C F B D E A) 
(A G F B D C E) 
(A B D G C F E) 
(G C A D E F B)

;; Set keyword arguments :start and :end to shuffle just a subsequence of the
;; given sequence
(loop repeat 4 
   do (print (multi-shuffle '(a b c d e f g) 3
                            :fix nil
                            :start 2
                            :end 5)))

=>
(A B D E C F G) 
(A B E C D F G) 
(A B E D C F G) 
(A B D C E F G)

SYNOPSIS

(defun multi-shuffle (seq num-shuffles &key 
                      (start 0) 
                      (end (length seq))
                      (copy t)
                      (fix t)
                      (reset t))

permutations/multi-shuffle-with-perms [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Return one permutation from a shuffled list of permutations of the
 specified list. The second argument determines how many shuffled
 permutations will be in the list from which the resulting permutation is
 selected. Similar to the "multi-shuffle" function, but uses the function
 "inefficient-permutations" as part of the process.

 The <num-shuffles> argument allows the user to always return the same
 specific permutation.

 NB: This function always uses a fixed random seed and has no optional
     arguments to allow the user to alter that setting.

ARGUMENTS

 - A list.
 - An integer that is the number of consecutive shuffles to be collected in
   the list from which the resulting permutation is selected.

RETURN VALUE

 - A list that is a single permutation of the specified list.

EXAMPLE

;; Returns a permutation of a shuffled version of the specified list
(let ((l '(0 1 2 3 4)))
  (multi-shuffle-with-perms l 7))

=> (3 1 4 2 0) 

;; Always returns the same result
(loop repeat 4 do (print (multi-shuffle-with-perms '(0 1 2 3 4) 7)))

=>
(3 1 4 2 0) 
(3 1 4 2 0) 
(3 1 4 2 0) 
(3 1 4 2 0)

;; Different <num-shuffles> values return different permutations
(loop for i from 0 to 5 
   do (print (multi-shuffle-with-perms '(0 1 2 3 4) i)))

=>
(0 1 2 3 4) 
(1 4 2 0 3) 
(0 3 1 4 2) 
(4 0 2 1 3) 
(1 2 3 4 0) 
(2 1 3 0 4)

SYNOPSIS

(defun multi-shuffle-with-perms (seq num-shuffles)

permutations/permutate [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Systematically produce a list of all possible permutations of an original
 list of elements of any type.

 NB: Such lists can quickly become very long, so slippery-chicken
     automatically defaults to outputting the resulting list to a file and 
     printing a warning when the results exceed a certain length. 

ARGUMENTS

 - A list with elements of any type.

OPTIONAL ARGUMENTS

 - allow-file: whether to allow the results to be written to a file rather
 than returned to the interpreter. This will only happen if the length of
 the list is > 8. The advantage is that you can then read in the file rather
 than slowly regenerate the results if you need them again.

RETURN VALUE

 A list of lists that are all possible permutations of the original,
 specified list.

 Interrupts with an error if the method is passed anything but a list. 

EXAMPLE

;; Simple usage
(permutate '(a b c))

=> ((A B C) (B A C) (A C B) (C A B) (B C A) (C B A))

;; When the list is more than 8 elements long, the resulting permutations are
;; written to a file due to the very high number of results
(permutate '(1 2 3 4 5 6 7 8 9))

=>
WARNING: permutations::permutations: This call will return 362880 
results so they are being written to the file 
'/tmp/permutations.txt'.

SYNOPSIS

(defun permutate (list &optional (allow-file t))

permutations/permutations [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Systematically produce a list of all possible permutations of a set of
 consecutive integers beginning with zero. The function's only argument,
 <level>, is an integer that determines how many consecutive integers from 0
 are to be used for the process.

 This is a more efficient permutation algorithm, but the results will always 
 be in a certain order, with the same number at the end until that
 permutation is exhausted, then the number below that etc. 

ARGUMENTS

 An integer that indicates how many consecutive integers from 0 are to be
 used for the process.

OPTIONAL ARGUMENTS

 - allow-file: whether to allow the results to be written to a file rather
 than returned to the interpreter. This will only happen if the length of
 the list is > 8. The advantage is that you can then read in the file rather
 than slowly regenerate the results if you need them again.

RETURN VALUE

 A list of sequences (lists), each of which is a permutation of the
 original. 

EXAMPLE

;; Produce a list consisting of all permutations that can be made of 4
;; consecutive integers starting with 0 (i.e., (0 1 2 3))
(permutations 4)

=>
((0 1 2 3) (1 0 2 3) (0 2 1 3) (2 0 1 3) (1 2 0 3) (2 1 0 3) (0 1 3 2)
 (1 0 3 2) (0 3 1 2) (3 0 1 2) (1 3 0 2) (3 1 0 2) (0 2 3 1) (2 0 3 1)
 (0 3 2 1) (3 0 2 1) (2 3 0 1) (3 2 0 1) (1 2 3 0) (2 1 3 0) (1 3 2 0)
 (3 1 2 0) (2 3 1 0) (3 2 1 0))

SYNOPSIS

(defun permutations (level &optional (allow-file t))

permutations/random-rep [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Return a random non-negative number that is less than the specified
 value. An optional argument allows for the random state to be reset.

ARGUMENTS

 - A number.

OPTIONAL ARGUMENTS

 - T or NIL to indicate whether the random state should be reset before the
   function is performed. T = reset. Default = NIL.  

RETURN VALUE

 A number.

EXAMPLE

  ;; By default returns a different value each time
  (loop repeat 10 do (print (random-rep 5)))
  
  =>
  1 
  3 
  4 
  4 
  3 
  4 
  2 
  0 
  2 
  0

  ;; Setting the optional argument to T resets the random state before
  ;; performing the function
  (loop repeat 10 do (print (random-rep 5 t)))

  =>
  3 
  3 
  3 
  3 
  3 
  3 
  3 
  3 
  3 
  3

SYNOPSIS

  (defun random-rep (below &optional (reset nil))

permutations/shuffle [ Functions ]

[ Top ] [ permutations ] [ Functions ]

DESCRIPTION

 Create a random ordering of a given sequence or a subsequence of a given
 sequence.  By default we used fixed-seed randomness so we can guarantee the
 same results each time (perhaps counter-intuitively).  So the order of the
 permutations returned will always be the same unless keyword argument :fix
 is set to NIL.  

 NB: This function is a modified form of Common Music's shuffle function.

ARGUMENTS

 - A sequence (list, vector (string)).

OPTIONAL ARGUMENTS

 keyword arguments:
 - :start. A zero-based index integer indicating the first element of a
   subsequence to be shuffled. Default = 0.
 - :end. A zero-based index integer indicating the last element of a
   subsequence to be shuffled. Default = the length of the given sequence.
 - :copy. T or NIL to indicate whether the given sequence should be copied
   before it is modified or should be destructively shuffled. 
   T = copy. Default = T.
 - :fix. T or NIL to indicate whether the given sequence should always be
   shuffled with the same (fixed) random seed (thus always producing the
   same result). T = fixed seed. Default = T.
 - :reset. T or NIL to indicate whether the random state should be reset
   before the function is performed.  T = reset. Default = T.

RETURN VALUE

 A list.

EXAMPLE

;; Simple shuffle with default keywords.
(shuffle '(1 2 3 4 5 6 7))

=> (5 4 3 6 7 1 2)

;; Always returns the same result by default.
(loop repeat 4 do (print (shuffle '(1 2 3 4 5 6 7))))

=>
(5 4 3 6 7 1 2) 
(5 4 3 6 7 1 2) 
(5 4 3 6 7 1 2) 
(5 4 3 6 7 1 2)

;; Set keyword argument :fix to NIL to return different results each time 
(loop repeat 4 do (print (shuffle '(1 2 3 4 5 6 7) :fix nil)))

=>
(1 2 6 3 5 4 7) 
(1 3 5 2 7 4 6) 
(4 7 2 5 1 6 3) 
(1 5 3 7 4 2 6)

;; Set the keyword argument :reset to t only at the beginning so we get the
;; same result that time but different (but repeatable) results thereafter.
(loop repeat 3 do
     (print 'start)
     (loop for i below 4 
        do (print (shuffle '(1 2 3 4 5 6 7) :reset (zerop i)))))

=>
START 
(5 4 3 6 7 1 2) 
(4 6 5 2 3 1 7) 
(3 4 1 6 5 7 2) 
(3 2 7 4 1 6 5) 
START 
(5 4 3 6 7 1 2) 
(4 6 5 2 3 1 7) 
(3 4 1 6 5 7 2) 
(3 2 7 4 1 6 5) 
START 
(5 4 3 6 7 1 2) 
(4 6 5 2 3 1 7) 
(3 4 1 6 5 7 2) 
(3 2 7 4 1 6 5) 


;; Set keyword arguments :start and :end to shuffle just a subsequence of the
;; given sequence
(loop repeat 4 
   do (print (shuffle '(1 2 3 4 5 6 7) 
                      :fix nil
                      :start 2
                      :end 5)))

=>
(1 2 5 4 3 6 7) 
(1 2 3 5 4 6 7) 
(1 2 4 5 3 6 7) 
(1 2 3 4 5 6 7)

SYNOPSIS

(defun shuffle (seq &key 
                (start 0) 
                (end (length seq))
                (copy t)
                (fix t)
                (reset t)
                &aux (width (- end start)))