Re: Help with Permutations
- From: mareg@xxxxxxxxxxxxxxxxxxxxxxxx ()
- Date: Sun, 8 Jan 2006 11:38:37 +0000 (UTC)
In article <43c06b71$0$163$edfadb0f@xxxxxxxxxxxxxxxxxxxx>,
"Jonas" <asdf@xxxxxxxxxxxxxxx> writes:
>
><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
>> 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.
Sorry for the ambiguity; the -1 is outside of the sum.
In fact 5023 is the correct answer when k1=1, k2=3, k3=k4=2, but, as quasi
correctly observed, for the string "acccdde", it should be
k1=1, k2=3, k3=2, k4=1.
Derek Holt.
.
- References:
- Help with Permutations
- From: barliow
- Re: Help with Permutations
- From:
- Re: Help with Permutations
- From: Jonas
- Help with Permutations
- Prev by Date: Re: Infinity
- Next by Date: Re: Help with Permutations
- Previous by thread: Re: Help with Permutations
- Next by thread: Re: Help with Permutations
- Index(es):
Relevant Pages
|
