Re: Help with Permutations
- From: quasi <quasi@xxxxxxxx>
- Date: Sun, 08 Jan 2006 05:17:58 -0500
On Sun, 08 Jan 2006 05:10:00 -0500, quasi <quasi@xxxxxxxx> wrote:
>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
Ugh.
I see the bugs now -- as I initially assumed, they were my bugs.
In my inner summation in program #1, and again in my inner loop in
program #2, I have a typo: instead of i4, I have 14. After fixing the
typos, both programs now give the correct result of 1265.
As an excuse, I'm legally blind without my glasses.
quasi
.
- References:
- Help with Permutations
- From: barliow
- Re: Help with Permutations
- From:
- Re: Help with Permutations
- From: quasi
- Help with Permutations
- Prev by Date: Re: why do computer scientists say 1KB=1024 bytes?!!
- Next by Date: Maximum possible chess moves
- Previous by thread: Re: Help with Permutations
- Next by thread: Re: Help with Permutations
- Index(es):
Relevant Pages
|
