[Edu-sig] More permutation madness [Cryptonomicon]

[Kirby Urner]

At 03:33 AM 11/30/2000 -0800, Daniel Yoo wrote:
>
>There was a question about ways of generating permutations: is there an
>easy way to show that these two functions:

<<SNIP>>

>act differently?

They have different properties.  There's only one possible
route to ABCD...WXYZ in the restricted method (all letters
self-identified) through a narrowing set of options at 
each turn, for 26 turns.  But the unrestricted method gives
a great many pathways to this same terminus in 26 iterations,
by presenting a non-narrowing set of options at each turn.

The restricted method is your classic decision tree with 
fanning branches, terminating in 26! equally probable 
outcomes.  Every iteration forces you to the next level,
towards the final outcome level.  The unrestricted method 
allows you to retrace your steps, back towards the 
beginning.

Without trying to compute a lot of specific probabilities,
I think you can see that the two methods, while confined 
to the same "state space" of 26! letter sequences, are 
not isomorphic (i.e. are not simply two ways of doing the 
exact same thing).

Kirby