aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorColin Okay <cbeok@protonmail.com>2020-07-10 12:37:24 -0500
committerColin Okay <cbeok@protonmail.com>2020-07-10 12:37:24 -0500
commitd4908b6a0eafa20c6dd6bb40f3e115b7ef2154bc (patch)
tree35475d9f42d02e67746708d1e25f1a5def0dcf62
parentae16aa6dffb4c2b660a4aa0a8cd0ed7b96f8f48a (diff)
better explanation in the permutations example
-rw-r--r--README.md27
1 files changed, 19 insertions, 8 deletions
diff --git a/README.md b/README.md
index cc7bacb..57d51ae 100644
--- a/README.md
+++ b/README.md
@@ -519,20 +519,30 @@ time. It is a good example of the usefulness of `inflate!`.
(if (= 1 (length vec)) (seq (list vec))
(let ((elem (elt vec 0))
(subperms (perms (make-array (1- (length vec))
- :displaced-to vec
+ :displaced-to vec ; share vec's memory
:displaced-index-offset 1
:element-type (array-element-type vec)))))
(inflate! (lambda (subperm) (thread-through elem subperm))
subperms))))
```
+The basic flow is:
+
+1. single out the first element of the vector
+2. generate permutations for the remainder of the vector
+3. return a generator that "adds back" the singled out element for
+ each possible spot.
The interesting bit about this is that we recursively compute
-generators on the sub-arrays in a classic divide-and-conquer way. The
-code is made signifiantly noisier by the use of displaced arrays, but
-is made signifiantly more memory efficient as well.
+permutation generators for the subvectors of `vec` in a classic
+divide-and-conquer way, and then use `inflate!` to combine those
+"generated sub-generators" into a single generator, which we return.
+
+The above code is made signifiantly noisier by the use of displaced
+arrays. Displaced arrays let us share memory with the original vector.
For each "sub permutation", we create a new generator using a
-generator constructor called `thread-through`.
+generator constructor called `thread-through`. This is the part where
+we "add back" the singled out element.
``` lisp
(defun thread-through (elem vec)
@@ -554,7 +564,8 @@ generator constructor called `thread-through`.
```
And this function uses a utility function called `fill-and-insert`
-that just fills a buffer:
+that just fills a buffer, which I pulled out into its own function for
+clarity:
``` lisp
@@ -617,8 +628,8 @@ And here's a quick demo of its use:
We could have generated all 121645100408832000 permutations of
"generators are cool", and, though it would have taken us an eternity
-(approximately 1000 years on a single core of my machine), the memory
-consumption would stay at an even keel.
+(a little more than 1000 years on a single core of my machine), the
+memory consumption would stay at an even keel.