Re: Help with Permutations

On Sat, 7 Jan 2006 15:08:19 +0000 (UTC),
mareg@xxxxxxxxxxxxxxxxxxxxxxxx () wrote:

>In article <1136584344.300707.31850@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> "barliow" <jack.c.barlow@xxxxxxxxx> writes:
>>Hi all,
>>
>>I'm not mathematically fantastic so I hope this makes sense.
>>
>>I've written an algorithm to generate all permutations of words from a
>>given alphabet.
>>
>>Alphabet:
>>
>>"abc"
>>
>>Gives permutations:
>>
>>a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bac, bca, cab, cba
>>
>>In order to keep track of the progress through the algorithm, I need to
>>be able to calculate the total number of permutations in advance. I can
>>do this using the following formula:
>>
>>Number of permutations of size k taken from n objects is:
>>
>> n!
>>n_P_k = --------
>> (n - k)!
>>
>>So I can calculate the total number of permutations off all lengths as:
>>
>>P = (3! / (3! - 1!)) + (3! / (3! - 2!)) + (3! / (3! - 3!)) = 15
>>
>>However, the algorithm is designed to eliminate repeated permutations
>>that arise as a result of having repeated letters:
>>
>>Alphabet:
>>
>>"acc"
>>
>>Gives permutations:
>>
>>a, c, ac, ca, cc, acc, cac, cca
>>
>>This means that the formula above no longer works. I'm wondering if
>>someone can provide a formula to calculate the total of number of
>>permutations of *all* lengths that will be outputted in the following
>>scenarios:
>>
>>"abc" (should = 15)
>>
>>"accd" (should = 34)
>>
>>"acccdde" (uncertain as to what the result should be)
>>
>
>I don't know a closed formula for this total number (which is not to say
>that there isn't one!) but it is not difficult to calculate it.
>
>Suppose k1, k2, ..., kr are the numbers of each of the distinct letters
>in your string. (For example, for "acccddee", k1=1, k2=3, k3=k4=2.)
>Then the total number of what you describe above as "permutations" is
>(view this in fixed width font):
>
> k1 k2 kr
> -- -- --
> \ \ \ (i1 + i2 + ... + ik)!
> > > . . . > ---------------------- - 1
> / / / i1! i2! ... ik!
> -- -- --
> i1=0 i2=0 ik=0
>
>(The -1 at the end is to avoid counting the empty string, which corresponds
>to i1=i2=...ir=0 in the sum.)
>
>You should be able to write a program to evaluate this expression for given
>k1, k2, ..., kr. Doing it for the example above, k1=1, k2=3, k3=k4=2
>gives 1265, as quasi reported.
>
>Derek Holt.

I implemented your iterated sum formula using Maple 9.5.

For the string "acccdde", my first attempt at implementing the formula
yielded, instead of 1265, a rather surprising answer:

549831041606246399

Obviously the above answer is way too big, so I tried to find the bug
in my program. I couldn't find it.

Since my first program was implemented as a function rather than as a
procedure, I decided to try rewriting it as a procedure instead. Same
incorrect result.

I did finally work around the error to get the correct answer, but I
still can't find the source of the error in the first 2 attempts.

At this point, I now think it's a Maple bug, but if it's my bug,
perhaps someone could tell me where I went wrong.

Here are the 2 implementations both of which gave the same incorrect
result: 549831041606246399

Program #1:

f:=(k1,k2,k3,k4)->
Sum(
Sum(
Sum(
Sum((i1+i2+i3+14)!/(i1!*i2!*i3!*i4!),
i4=0..k4),
i3=0..k3),
i2=0..k2),
i1=0..k1)-1;

f(1,3,2,1);
value(%);

Program #2:

g:=proc(k1,k2,k3,k4)
local s,i1,i2,i3,i4;
s:=0;
for i1 from 0 to k1 do
for i2 from 0 to k2 do
for i3 from 0 to k3 do
for i4 from 0 to k4 do
s:=s+(i1+i2+i3+14)!/(i1!*i2!*i3!*i4!);
od;
od;
od;
od;
s-1;
end:

g(1,3,2,1);

Could someone please verify the bug? Is it my bug or Maple's bug?

quasi
.

Relevant Pages

  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >> gives 1265, as quasi reported. ... either Maple has a bug or there's a bug in my program. ...
    (sci.math)
  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >> Derek Holt. ... >is inside the sum or outside but not 1265. ...
    (sci.math)
  • Re: Help with Permutations
    ... >>given alphabet. ... >>Gives permutations: ... >>In order to keep track of the progress through the algorithm, ... I have calculated your sum and I get 4952 or 5023 depending on if the one ...
    (sci.math)
  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >I implemented your iterated sum formula using Maple 9.5. ... >Obviously the above answer is way too big, so I tried to find the bug ...
    (sci.math)
  • Re: Help with Permutations
    ... to remove duplicates. ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... > is inside the sum or outside but not 1265. ...
    (sci.math)