[Tutor] A small math puzzle [recreational Python]

[Lloyd Hugh Allen]

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.