Permutation generator 2

by Stephen R. Schmitt

Contents

1. About
2. The source code
3. Discussion

1. About

This is a Java Script calculator that counts the number of permutations in a set of n objects where there are duplicates; it can list those permutations.

To operate the calculator, enter a word that represents objects as characters. Press the Count button to compute the number of permutations. Press the Listing button to compute the result and generate a listing of permutations.

Note that the generator is case sensitive; 'a' is different from 'A'. Also, spaces are counted as characters.

Return to Contents

2. The source code

The Java Script source code for this program can be viewed by using the View|Source command of your web browser.

You may use or modify this source code in any way you find useful, provided that you agree that the author has no warranty, obligations or liability. You must determine the suitability of this source code for your use.

Return to Contents

3. Discussion

number of permutations

The number of distinct permutations of n objects where n₁ of the objects are identical, n₂ of the objects are identical, ···, n_r of the objects are identical is found by: :

     n!
-----------
n1!n2!···nr!

 4!
--- = 12
 2!

  6!
----- = 180
 2!2!

listing the permutations

An algorithm to generate permutations is shown below. Starting from an initial a combination of objects, it computes subsequent permutations in lexicographic order. The algorithm will generate all permutations for a given combination of objects if the initial combination is the first in lexicographic order.

valuei <-- ai

loop

    i <-- k - 1                         % find place to start
    while valuei-1 >= valuei 
        decr i
    end while

    exit when i < 1                     % all in reverse order

    j <-- k                             % do next permutation
    while valuej-1 <= valuei-1 
        decr j
    end while

    swap valuei-1, valuej-1

    incr i 
    j <-- k

    while i < j                         % need more swaps
        swap valuei-1, valuej-1
        incr i
        decr j
    end while

end loop

See Also

Permutation generator that counts the number of permutations of k objects in a set of n objects.

Permutation generator Zeno source code to generate permutations of k objects in a set of n objects.

Return to Contents