[Tutor] A small math puzzle [recreational Python]

[Lloyd Hugh Allen]

Oops. Wrong puzzle. Now I feel sheepish. Seems related though (and it's
how I had remembered the puzzle until I reread my own post).

Sorry 'bout that.

Lloyd Hugh Allen wrote:
> 
> Danny Yoo wrote:
> >
> > On Sat, 5 Jan 2002, Lloyd Hugh Allen wrote:
> >
> > > Danny Yoo wrote:
> > > > However, here's an example that is a rearrangement but doesn't work
> > > > because it has a fixed letter:
> > > >
> > > >     'TRESAE'
> > > >      ^
> > > >
> > > > In this example, the 'T' makes this rearrangement inacceptable, since
> > > > 'TERESA' itself begins with a 'T' too.
> > > >
> > > > The puzzle is to write a program that counts all the possible
> > > > rearrangements without fixed letters.
> > > >
> > > > Have fun!
> > >
> > > Is it necessary to actually construct the list of rearrangements, or
> > > do you just want a function that will compute how many rearrangements
> > > exist?
> >
> > If you can think of a way to do it without actually generating the
> > rearrangements, that would be great!
> >
> > _______________________________________________
> > Tutor maillist  -  Tutor@python.org
> > http://mail.python.org/mailman/listinfo/tutor
> 
> I know that this is late, but I just came across this while teaching
> combinatorics in precalculus--
> 
> if you have n spaces to fill with objects that occur e1, e2, e3, ...
> etc. times, (e.g., "TERESA" has six spaces, and 'E' occurs twice), the
> number of DISTINCT PERMUTATIONS (which is what you would check an index
> for if you were interested in such things) is
> 
> n!/(e1!e2!e3!...)
> 
> e.g./
> 
> 6!/(2!1!1!1!1!) == 6!/(2!)
> 
> The cleverest algorithm for evaluating that puppy while trying really,
> really hard to avoid Longs would probably try to find common factors
> between the factors of n! and the denominator, since multiplying and
> then dividing is slow and costly where smart multiplying is cheap. Each
> factor of the denominator should either appear or share a factor with a
> factor of the numerator (take for instance 4!/(2!2!)--every other
> integer is even, and so every other integer is divisible by two; 4!,
> having four consecutive integers for factors, is guaranteed to have two
> exactly two even factors).
> 
> Or something.
> 
> Sorry to bring up old business. And sorry also if someone else had
> already posted this algorithm and I had missed it--I looked back through
> my python-tutor folder and couldn't find mention of this formula.
> 
> As for why, n! gives the number of permutations; the denominator tells
> us how many distinct ways we could arrange the parts that we consider to
> be identical. Spraypaint one of the 'E's red and the other blue, and for
> each arrangement of TERESA, there are two distinct ways to arrange our
> 'E's. And so on for more repeated events.
> 
> I'll stop blathering now.