Vlorbik's Diner

son of owen's cooking show

632

Posted by vlorbik on November 17, 2009

a couple days ago i discussed a
technique for listing all
the permutations of a (small)
set. essentially this.

count the elements.
suppose there are n of ’em.
there are n! (en-factorial) permutations.

our first letter… element…
whatever it is…
will be the first letter (say) *of*
the *same* number of permutations
as will the second letter
(or *any* letter… any element
of the set-to-be-permuted).
so we can say
that each letter begins (1/n)th
(one-enth) of the list.
note that (1/n)*n! = (n-1)!
and write out this many copies
of each letter in columns.
end of step one.

for {E,G,B,D,F}… the example
i “assigned”… my first inclination
is to remark that
{E,G,B,D,F} = {B,D,E,F,G}
(sets do *not* depend on order)
and so one could begin as follows.

B____ D____ E____ F____ G____
B____ D____ E____ F____ G____
B____ D____ E____ F____ G____
B____ D____ E____ F____ G____
.
.
.
B____ D____ E____ F____ G____

(24 rows… there are 5!= 120
permutations to discover
and 1/5 *of* ’em start with B:
so there are 24 B’s. etcetera.)

in step two we’ll fill in the
*second* letter of each permo.
consider the B column only
(for now). there are four
“remaining” letters. each
will appear as the *next*
letter just as many times
as each of the others:
this is 1/4 of the total…
of 24 B’s… and so *six*.
“count by sixes” down the
first column: 6 D’s, then
6 E’s, and so on down.

BD___ D____ E____ F____ G____
BD___ D____ E____ F____ G____
BD___ D____ E____ F____ G____
BD___ D____ E____ F____ G____
BD___ D____ E____ F____ G____
BD___ D____ E____ F____ G____

BE___ D____ E____ F____ G____
BE___ D____ E____ F____ G____
BE___ D____ E____ F____ G____
BE___ D____ E____ F____ G____
BE___ D____ E____ F____ G____
BE___ D____ E____ F____ G____

BF___ D____ E____ F____ G____
.
.
.
BG___ D____ E____ F____ G____

be sure you see what’s going on:
all the ideas are in place i think.
if it’s clear why we’re creating
120 entries in 24 rows and why
we counted by 6’s in this step,
everything else should fall into
place pretty easily i hope.

count by sixes throughout *each*
column, omitting whatever letter
has “already been used” of course.

BD___ DB___ EB___ FB___ GB___
BD___ DB___ EB___ FB___ GB___
BD___ DB___ EB___ FB___ GB___
BD___ DB___ EB___ FB___ GB___
BD___ DB___ EB___ FB___ GB___
BD___ DB___ EB___ FB___ GB___

BE___ DE___ ED___ FD___ GD___
BE___ DE___ ED___ FD___ GD___
BE___ DE___ ED___ FD___ GD___
BE___ DE___ ED___ FD___ GD___
BE___ DE___ ED___ FD___ GD___

BF___ …
.
.
.
BG___ DG___ EG___ FG___ GF___

each column falls into groups
of six unfinished permutations
as of now. each such set has
two letters present and hence
three letters left to “choose
from”. one-third of six is two
so considering “BD” (for example)
we’ll add *two* E’s, *two* F’s,
and *two* G’s.

and likewise for *each* of the
sets-of-six: count off
“missing” letters by twos.

BDE__ DB___ EB___ FB___ GB___
BDE__ DB___ EB___ FB___ GB___
BDF__ DB___ EB___ FB___ GB___
BDF__ DB___ EB___ FB___ GB___
BDG__ DB___ EB___ FB___ GB___
BDG__ DB___ EB___ FB___ GB___

BED__ …
.
.

(one is actually *saying*
“eee, eee, eff, eff, gee, gee”
during this step when working
with a fellowstudent typically).

fill in all the columns by the
same procedure. one now has
a collection of 60 pairs of
three-letter strings.
complete the strings by
attaching their two “missing” letters:
once in one order and once in the other.

of the two BDE’s, for example,
one becomes BDEFG
and the other BDEGF.

this completes the whole ordeal.

BDEFG DBEFG ….
BDEGF
BDFEG
BDFGE
BDGEF
BDGFE

BEDFG
.
.
.

more later. madeline’s awake.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: