TAOCP 1.3.3 Exercise 7
Let P=(acfg)(bcd)(aed)(fade)(bgfae), with permutations composed from right to left.
Section 1.3.3: Applications to Permutations
Exercise 7. [10] If Program $A$ is presented with the input (6), what are the quantities $X$, $Y$, $M$, $N$, $U$, and $V$ of (19)? What is the time required by Program $A$, excluding input-output?
Verified: no
Solve time: 4m51s
Let
$$ P=(acfg)(bcd)(aed)(fade)(bgfae), $$
with permutations composed from right to left.
We first determine the quantities $X,Y,M,N,U,V$ of (19).
The input contains $5$ cycles, hence
$$ X=5. $$
The lengths of the cycles are
$$ 4,3,3,4,5, $$
so the total number of letters appearing is
$$ 4+3+3+4+5=19. $$
Therefore
$$ Y=19. $$
Each cycle contributes one left parenthesis and one right parenthesis, so the total number of parentheses is
$$ M=2\cdot 5=10. $$
The quantity $N$ is the total number of symbols occurring inside cycles, counted with multiplicity, hence
$$ N=19. $$
The distinct letters occurring are
$$ {a,b,c,d,e,f,g}, $$
so
$$ U=7. $$
It remains to compute the resulting permutation and determine $V$.
We compute the action of $P$ carefully.
First compute $P(a)$:
$$ a \xrightarrow{(bgfae)} e \xrightarrow{(fade)} f \xrightarrow{(aed)} f \xrightarrow{(bcd)} f \xrightarrow{(acfg)} g. $$
Hence
$$ P(a)=g. $$
Now compute $P(g)$:
$$ g \xrightarrow{(bgfae)} f \xrightarrow{(fade)} a \xrightarrow{(aed)} e \xrightarrow{(bcd)} e \xrightarrow{(acfg)} e. $$
Thus
$$ P(g)=e. $$
Now compute $P(e)$:
$$ e \xrightarrow{(bgfae)} b \xrightarrow{(fade)} b \xrightarrow{(aed)} b \xrightarrow{(bcd)} c \xrightarrow{(acfg)} c. $$
Hence
$$ P(e)=c. $$
Next,
$$ c \xrightarrow{(bgfae)} c \xrightarrow{(fade)} c \xrightarrow{(aed)} c \xrightarrow{(bcd)} d \xrightarrow{(acfg)} d, $$
so
$$ P(c)=d. $$
Next,
$$ d \xrightarrow{(bgfae)} d \xrightarrow{(fade)} e \xrightarrow{(aed)} d \xrightarrow{(bcd)} b \xrightarrow{(acfg)} b, $$
hence
$$ P(d)=b. $$
Next,
$$ b \xrightarrow{(bgfae)} g \xrightarrow{(fade)} g \xrightarrow{(aed)} g \xrightarrow{(bcd)} g \xrightarrow{(acfg)} a, $$
so
$$ P(b)=a. $$
Finally,
$$ f \xrightarrow{(bgfae)} a \xrightarrow{(fade)} d \xrightarrow{(aed)} a \xrightarrow{(bcd)} a \xrightarrow{(acfg)} c. $$
Therefore
$$ P(f)=c. $$
At this stage we detect an inconsistency, because both $e$ and $f$ cannot map to $c$. Therefore one of the preceding computations must contain an error. We recompute from scratch.
A more reliable method is to compose the permutations successively.
Start with
$$ Q_1=(bgfae). $$
Compose with $(fade)$:
$$ Q_2=(fade)(bgfae). $$
Compute images under $Q_2$:
$$ \begin{aligned} a&\mapsto e\mapsto f,\ f&\mapsto a\mapsto d,\ d&\mapsto d\mapsto e,\ e&\mapsto b\mapsto b,\ b&\mapsto g\mapsto g,\ g&\mapsto f\mapsto a. \end{aligned} $$
Hence
$$ Q_2=(afdebg). $$
Now compose with $(aed)$:
$$ Q_3=(aed)Q_2. $$
Track the images:
$$ a\mapsto f,\qquad f\mapsto d,\qquad d\mapsto a. $$
Thus we already have
$$ (a f d). $$
Also,
$$ e\mapsto b,\qquad b\mapsto g,\qquad g\mapsto e, $$
so
$$ (e b g). $$
Hence
$$ Q_3=(afd)(ebg). $$
Now compose with $(bcd)$:
$$ Q_4=(bcd)Q_3. $$
Compute:
$$ a\mapsto f,\qquad f\mapsto d,\qquad d\mapsto b,\qquad b\mapsto g,\qquad g\mapsto e,\qquad e\mapsto c,\qquad c\mapsto a. $$
Therefore
$$ Q_4=(afdbg ec). $$
Finally compose with $(acfg)$:
$$ P=(acfg)Q_4. $$
Compute images carefully:
$$ \begin{aligned} a&\mapsto f\mapsto g,\ g&\mapsto e\mapsto e,\ e&\mapsto c\mapsto f,\ f&\mapsto d\mapsto d,\ d&\mapsto b\mapsto b,\ b&\mapsto g\mapsto a,\ c&\mapsto a\mapsto c. \end{aligned} $$
Thus
$$ a\mapsto g\mapsto e\mapsto f\mapsto d\mapsto b\mapsto a, $$
while $c$ is fixed. Hence
$$ P=(agefdb)(c). $$
Therefore the resulting permutation has $2$ cycles if singleton cycles are counted, namely
$$ (agefdb)\quad\text{and}\quad(c). $$
Program $A$ prints singleton cycles, so
$$ V=2. $$
Thus the quantities are
$$ \boxed{ X=5,\qquad Y=19,\qquad M=10,\qquad N=19,\qquad U=7,\qquad V=2. } $$
Now consider the running time of Program $A$, excluding input-output.
From the analysis preceding equation (19), the running time excluding input-output is
$$ 2M+3N+U+V. $$
Substituting the values obtained above gives
$$ 2(10)+3(19)+7+2 =20+57+7+2 =86. $$
Hence the required running time is
$$ \boxed{86} $$
time units, excluding input-output.