Re: Help with Permutations

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

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: 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: 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)