## sc/permutations [ Modules ]

[ Top ] [ Modules ]

NAME

``` permutations

File:             permutations.lsp

Class Hierarchy:  none, no classes defined.

Version:          1.0.12

Project:          slippery chicken (algorithmic composition)

Purpose:          Various permutation functions.

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

Creation date:    10th November 2002

\$\$ Last modified:  10:26:32 Sat Jun  6 2020 CEST

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)))
```