there is no frigate like a boat

in recent posts i’ve typed out
rather detailed descriptions
of a fairly simple process:
forming lists of all the
permutations of a given
(small) finite set.
four or five elements, say.

any more than five
would be impractical for in-class work
though i can easily imagine assigning a
“neatness counts” *poster* project along
the lines “create a display showing…
exactly once each, prominently and distinctly…
all 720 permutations of the set
{A,B,C,D,E,F}”. you fail if it’s wrong
of course so check it over several times…
by several different methods if
possible (usually one settles for two
actually… but this is math ed so
the more the better [let’s pretend]).

so i now propose to look at methods
of *generating* our lists. thus far
we’ve examined what i hope is much
the commonest: trees.

given the symbols of {@, ^, *}
(“at, hat, and splat”) to permute.
let’s see if i can draw it
with this typer here.

[tries and fails; that would be “no”.]

to heck with it then. the point is,
you can draw what’s called a tree.

[
this is as good a time as any to mention
that if there were any doubt in anyone’s
mind what the heck i’m going on about
they’d take advantage of the web format
and enter a few well-chosen words into
the search engine of their choice. what
would owen do. quite often i tack “wiki”
onto the end of my search string (i.e.,
my list of words to search *for*) so as
to be taken quickly to the amazingly
useful wikipedia (the pearl of the net).
on “tree diagram” it’s *not* so useful
but you’ll see a real one quick enough
if you do the search. think “family
tree” by the way if you haven’t seen
the connection yet….
]

@
@

^
^

*
*

each pair… the ats, the hats, the splats…
should be imagined… since i’m helpless to
*draw* it… as connected by “branches”
to a “root” to the left of the left margin.

*three* branches at this stage…
one for each of the “objects to be permuted”.

in the next stage, two branches
sprout from each of our current ones:

@^
@*

^@
^*

*@
*^

(the “at” is here imagined as having
sprouted new leaves: one for “hat”
and one for “splat”… and so on down
[*two* leaves for each new set because
there are two “unused” symbols
left to permute]).

there are no more “choices to make”:
we can complete each partial-permutation
at this stage by appending the
only-available-symbol. and of course
we get
@^*, @*^, ^@*, ^*@, *@^, *^@
: i hereby propose to call this
the tree order for the
permutations of the symbols
in the (ordered) list [@, ^, *].

note that this “tree” procedure
vividly illustrates the “factorial”
process. there are six orders
because 6 = 3*2*1…
three choices of first letter
(the first set of branches),
two of the next… so on.

this “tree” algorithm is exactly that
of the previous posts; if this isn’t
obvious i urge you (strongly) to
write out the tree for [A,B,C,D]
and compare your result to
(what i’ve already posted)
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
CDAB
DABC
DACB
DBAC
DBCA
DCAB
DCBA

now it’s no coincidence that this
is not only *tree* order but
*alphabetical* order…
also known as “dictionary”
or “lexicographic” order.
this can be very helpful when
alphabetical symbols are used.

alphabetical order is actually a technique
of astonishing power. this is why we must
endure shrill voices *singing* the damn
thing over and over, and even encourage
them to continue until they’re sure they
have it right, and to teach others, and to
correct mistakes whenever they’re encountered.

once you can find words in a dictionary
you’ve got it made: you don’t need
teachers to learn what words mean
anymore. just tools and motivation.

back to permutations.
where i believe something very similar
is going on.

a hugely important point:
“list the permutations”
calls for full credit when
the permutations are given
in *any* order. hard work
for the grader then. too bad.

my {ABCD, ABDC, …, DCBA},
listed alphabetically, is no better or worse
(unless there were more *rules* imposed)
than any other.

i think… vaguely… of our “tree” method
as *top-down*. we’ve got four letters
so we spread ’em out onto different
parts of our working space and work
“down” the list.

by contrast, a “bottom-up” method might
examine a *single* permutation… the
“standard” ABCD, say… and work “up”
from there. as follows.

suppose i decide to “move letters”
in producing new permos from old.
start at the end with D. move it
as far as it’ll go.

ABCD
ABDC
ADCB
DABC

that’s it for strings having A, B, C
in their standard order. what’s next?
well suppose we reposition the C
one step leftward and repeat.

ACBD
ACDB
ADCB
DACB

so on (“reposition” C again and slide the D’s)

CABD
CADB
CDAB
DCAB

and so on (we’ve “gone as far as we can”
moving D’s and C’s only… so B is up next.
and so on:

BACD
BADC
BDAC
DBAC
BCAD
BCDA
BDCA
DBCA
CBAD
CBDA
CDBA
DCBA

notice that
once having “repositioned” C
for the first time we then
“go through a D subroutine”.
we then reposition the C again
and go through the D-subroutine
again. until we can’t repostion C.

we then reposition *B* and go through
the C-and-D subroutine
(consisting of running *several* D-routines).

the towers of hanoi should be mentioned around here.

that’s it for now; i hope there’s somebody still following.
exercise. take a hostage and don’t let ’em go
until they satisfy you that they can write out all 24
permuations of {A, ?, 17, e}.