Re: Help with Permutations


<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.



.

Relevant Pages

  • Re: Strategy or Iterator?
    ... private int count; ... Dijkstra's algorithm generates permutations, ... All possible subsequences of length N of the input (considered to be ...
    (comp.lang.java.programmer)
  • 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: Permuatations [was: Please Help!!Daughter...]
    ... mathematical purity of exchanging elements. ... ", and then unifies them into a framework based on exchanges), ... It isn't that I don't know how to generate permutations. ... generate-and-discard algorithm with a bit of early pruning). ...
    (comp.lang.java.programmer)
  • Re: Javascript Best Practices Document v1.0
    ... or is it not a general algorithm. ... Today you assert that the algorithm becomes 'general' when it applies to ... An algorithm that is totally specific to a single context ... permutations. ...
    (comp.lang.javascript)
  • 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)