Re: Help with Permutations
- From: quasi <quasi@xxxxxxxx>
- Date: Sun, 08 Jan 2006 04:29:24 -0500
On Sun, 8 Jan 2006 02:31:26 +0100, "Jonas" <asdf@xxxxxxxxxxxxxxx>
wrote:
>
><mareg@xxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
>news:dpolh3$im4$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>> 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
I think you meant k1=1, k2=3, k3=2, k4=1.
>> gives 1265, as quasi reported.
>>
>> Derek Holt.
>
>I have calculated your sum and I get 4952 or 5023 depending on if the one
>is inside the sum or outside but not 1265.
>
The "1" is outside since it's intended to remove one case from the
count.
However Derek Holt's formula does correctly give a result of 1265 for
the example in question, so check your program.
quasi
P.S.
I implemented the formula in Maple and in my initial implementation,
instead of 1265, I got the following ridiculous answer:
549831041606246399
Obviously, either Maple has a bug or there's a bug in my program. By
default, I would assume the bug is mine, however the program is so
simple as to be self evidently correct.
However I was able to work around the bug, revising the program
slightly, and achieving the correct result.
I'll report the bug in a separate reply.
quasi
.
- Follow-Ups:
- References:
- Help with Permutations
- From: barliow
- Re: Help with Permutations
- From:
- Re: Help with Permutations
- From: Jonas
- Help with Permutations
- Prev by Date: Re: Euler's Formula
- Next by Date: Re: Linear embeddings of graphs
- Previous by thread: Re: Help with Permutations
- Next by thread: Re: Help with Permutations
- Index(es):
Relevant Pages
|
