Permutations
+ Associated files
NB: An exercise relating to the material covered in this tutorial can be found on the Exercises page.
slippery chicken comes with a number of predefined
algorithmic functions that are designed to help the user generate new
lists from existing ones by making variations of the original lists or
their elements. These functions all fall under the general category
of permutations, and can be found in
the permutations.lsp source file. This page will provide
a brief introduction to the most frequently used of these
functions.
General attributes of the permutation functions
All of the permutation functions in slippery chicken use a
random algorithm that defaults to a fixed-seed
state. This means that random operations return the same results each
time they are started (providing they are run on the same Lisp). Most
of the functions have optional arguments that allow the user to reset
the random seed, as well as to disable it.
The individual permutation functions
+ permutations
The permutations function systematically generates a
list of all possible permutations of a set of consecutive integers
beginning with zero. It takes as its only argument an integer that
indicates the number of consecutive numbers
(including 0) to use. In other words, calling the
function with 4 will produce permutations of the
numbers 0, 1, 2, and 3.
The order of the resulting list of permutations will be the same each time the function is called.
(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))
+ inefficient-permutations
The inefficient-permutations function returns a
randomly shuffled, non-systematic list of all possible permutations
of a set of consecutive integers starting with zero. It's only
required argument is an integer, which, like
the permutations function, indicates the number of
consecutive numbers (starting from 0) to use.
This function also has the three optional keyword
arguments :max, :skip,
and :fix.
The :max argument takes an integer that indicates the
maximum number of permutations to return.
The :skip argument takes an integer that indicates the
number of permutations of those returned that should be skipped. This
number always applies to consecutive permutations from the beginning
of the list.
The :fix argument takes T
or NIL to indicate whether the random shuffling of the
list of permutations returned should be performed with the same
(fixed) random seed each time or not. T indicates that a
fixed seed should be used.
(inefficient-permutations 4 :max 7 :skip 2 :fix t) => ((2 0 3 1) (1 0 2 3) (1 2 3 0) (0 2 3 1) (2 1 0 3))
+ permutate
The permutate function produces a list of all possible
permutations of an original list of specified elements of any
type.
NB: These lists get very long very fast! A list of 5 elements, for example, returns a new list of 120 elements; an original list of 6 elements produces a new list of 720. Original lists that have more than 8 elements cause the function to write the results to a file rather than to the print buffer.
(permutate '(a b c d))
=> ((A B C D) (B A C D) (A C B D) (C A B D) (B C A D) (C B A D) (A B D C)
(B A D C) (A D B C) (D A B C) (B D A C) (D B A C) (A C D B) (C A D B)
(A D C B) (D A C B) (C D A B) (D C A B) (B C D A) (C B D A) (B D C A)
(D B C A) (C D B A) (D C B A))
+ inefficiently-permutate
The inefficiently-permutate function returns a randomly
shuffled, non-systematic list of all possible permutations of an
original list of elements of any type. The new list is returned as a
flat list by default.
NB: These lists get very long very fast! Original lists of 8 or more elements result in the function's output being written to a file.
In addition to the one required argument of the list to be
permutated, this function has the four optional keyword
arguments :max, :skip, :fix,
and :sublists.
The :max argument takes an integer that indicates the
maximum number of permutations to return.
The :skip argument takes an integer that indicates the
number of permutations of those returned that should be skipped. This
number always applies to consecutive permutations from the beginning
of the list.
The :fix argument takes T
or NIL to indicate whether the random shuffling of the
list of permutations returned should be performed with the same
(fixed) random seed each time or not. T indicates that a
fixed seed should be used.
The :sublists argument takes .T
or NIL to indicate whether the permutations are to be
returned as a list of sublists (T) or as a flat
list.
(inefficiently-permutate '(a b c d) :max 7 :skip 2 :fix t) => (C A D B B A C D B C D A A C D B C B A D) (inefficiently-permutate '(a b c d) :max 7 :skip 2 :fix t :sublists t) => ((C A D B) (B A C D) (B C D A) (A C D B) (C B A D))
+ shuffle
The shuffle function creates a random ordering of a
given list or segment of a given list. In addition to its required
argument of the list to shuffle, it also has the five optional
keyword
arguments :start, :end, :copy,
:fix and :reset.
The :start argument takes a 0-based integer to indicate
the index of the first element of the list to be shuffled.
The :end argument takes a 0-based integer to indicate
the index of the last element of the list to be shuffled.
The :copy argument takes a T
or NIL to indicate whether the process is to be applied
to a copy of the list (T) or to the original instance of
the list (destructive).
The :fix argument takes a T
or NIL to indicate whether the operation is to be
performed with the same (fixed) random seed (T) or
not.
The :reset argument takes a T
or NIL to indicate whether the Lisp's random state is to
be reset (T) or not before applying the operation.
(shuffle '(1 2 3 4 5 6 7) :start 1 :end 5 :fix t :reset t) => (1 5 4 3 2 6 7)
+ multi-shuffle
The multi-shuffle function repeatedly applies
the shuffle function a specified number of times to a
specified list. In addition to its two required arguments of the list
to shuffle and the number of times to shuffle it, it also has the
five optional keyword
arguments :start, :end, :copy,
:fix and :reset.
The :start argument takes a 0-based integer to indicate
the index of the first element of the list to be shuffled.
The :end argument takes a 0-based integer to indicate
the index of the last element of the list to be shuffled.
The :copy argument takes a T
or NIL to indicate whether the process is to be applied
to a copy of the list (T) or to the original instance of
the list (destructive).
The :fix argument takes a T
or NIL to indicate whether the operation is to be
performed with the same (fixed) random seed (T) or
not.
The :reset argument takes a T
or NIL to indicate whether the Lisp's random state is to
be reset (T) or not before applying the operation.
(multi-shuffle '(1 2 3 4 5 6 7) 11 :start 1 :end 5 :fix t :reset t) => (1 5 3 4 2 6 7)
+ multi-shuffle-with-perms
The multi-shuffle-with-perms function returns one
permutation of a shuffled version of the specified list. It takes as
its two arguments the list to shuffle and an integer that indicates
the number of consecutive shuffles to be collected in the list from
which the resulting permutation is selected. This function always
uses a fixed random seed.
(multi-shuffle-with-perms '(0 1 2 3 4) 7) => (3 1 4 2 0)
+ move-repeats
The move-repeats function does not create permutations
per se, but can be used to remove any consecutive
repetitions of elements in existing lists, such as those created by
the other permutation functions listed above.
This function moves, when possible, one of any two elements of a list that are repeated consecutively to the first point in the list where no consecutive repetition is created. It only moves elements to the right. If no non-repeating place can be found in the remainder of the list, the element is moved to the end of the list.
This function can be applied to both simple lists and lists of sublists. If it is used with sublists, the last element of each sublist is checked for repetition with the first element of the next.
(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) (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))
+ random-rep
Like the move-repeats function,
the random-rep function does not create
permutations per se. It is mentioned here, however, since
its function is related to the manner by which many of the
permutation functions operate.
Like Lisp's own random function, this function returns
a pseudo-random, non-negative number that is less than the value
specified as its first (required)
argument. The random-rep function then has an
additional, optional argument (T or NIL)
that allows for the random state to be reset, allowing for the same
list of pseudo-random numbers to be produced at each call.
(loop repeat 10 collect (random-rep 5)) => (2 4 0 4 4 2 1 3 2 4) (loop repeat 10 collect (random-rep 5 t)) => (3 3 3 3 3 3 3 3 3 3)
+ Using the permutation functions in a piece
Any of the permutation functions can be used, of course, to generate self-referential lists of any kind of element, and can therefore be implemented to algorithmically generate any kind of slippery chicken data.
The following example code uses
the inefficiently-permutate function to algorithmically
generate the rhythm sequences of the rthm-seq-palette
for the piece
(let* ((perms (inefficiently-permutate '(e (e) s (e.) q s s (e))
:max 91
:sublists t))
(mini
(make-slippery-chicken
'+mini+
:ensemble '(((fl (flute :midi-channel 1))
(ob (oboe :midi-channel 2))
(bn (bassoon :midi-channel 3))))
:tempo-map '((1 (q 84)))
:set-palette '((0 ((fs2 b2 d4 a4 d5 e5 a5 d6)))
(1 ((b2 fs3 d4 e4 a4 d5 e5 a5 d6)))
(2 ((cs3 fs3 e4 a4 e5 a5 e6)))
(3 ((fs2 cs3 e4 a4 b4 e5 a5 b5 e5)))
(4 ((d2 a2 e4 fs4 gs4 b4 e5 b5)))
(5 ((a2 e3 e4 fs4 gs4 b4 cs5 e5 b5)))
(6 ((cs3 fs3 fs4 gs4 a4 cs5 a5 cs6)))
(7 ((fs2 cs3 fs4 gs4 a4 b4 cs5 fs5)))
(8 ((e2 a2 cs4 fs4 gs4 a4 b4 e5 gs5 b5 e6)))
(9 ((d2 a2 fs4 gs4 a4 e5 a5 e6)))
(10 ((a2 d2 e4 fs4 a4 e5 a5))))
:set-limits-high '((ob (0 a5 100 a5))
(bn (0 g3 100 g3)))
:set-limits-low '((fl (0 d5 100 d5)))
:set-map `((1 ,(loop for sn from 0 below (length perms)
collect (mod sn 11)))) ; mod 11 = 11 sets
:rthm-seq-palette (loop for p in perms
for rs-id from 0
collect `(,rs-id
((((4 4) ,@(nth rs-id perms)))
:pitch-seq-palette ((1 3 2 5 6)))))
:rthm-seq-map `((1 ((fl
,(loop for rs from 0 below (length perms)
collect rs))
(ob
,(loop for rs from 0 below (length perms)
collect
(mod (1+ rs) (length perms))))
(bn
,(loop for rs from 0 below (length perms)
collect
(mod (+ rs 2) (length perms))))))))))
(auto-beam mini t nil)
(map-over-bars mini 1 nil nil #'consolidate-rests-max)
(auto-slur mini '(fl ob bn))
(midi-play mini)
(cmn-display mini)
(write-lp-data-for-all mini))
 |