sc/permutations [ 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)))