Enumerator and Generator - handles Duplicates/Multiples
Terminology used here. A set (or group) is composed of one or more elements and each element is unique. A multiset (or group) is composed of one or more elements and some could be the same. A permutation of the group is the elements arranged in a particular order and number (fixed) of elements in the permutation could be less than the total number of elements in the group. The total number of elements in the group is assigned to the variable N here, and R is the fixed number of elements in a permutation, where R <= N. These are known as R-Permutations or R-Combinations. For a Combination, the order does not matter. The other elements that are the same kind are called either duplicates or multiples (We're using the terms interchangeably here). When we refer to the count of duplicates, we mean the total count of all the elements of a particular kind -- not just the additional ones that are the same. For instance, the word DAFFODIL has eight elements (letters in this case). The counts of duplicates/multiples are two for 'D' and two for 'F'.
Here 'enumerating' means the process of counting all the unique permutations (or combinations). (The first sense of the word: "to ascertain the number of") Though a group could be a multiset, the set (list) of permutations is a plain set for the processing here -- no mutliples.
Also 'generating' is the process of creating all the unique permutations (or combinations). In case of this program,
the permutations or combinations are not only generated in some data structure,
they are also actually listed on a web page (up to 50,000).
Note: I've borrowed most of this terminology from Donald Knuth's book, The Art of Computer Programming (TAOCP) Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005), v+128pp. ISBN 0-201-85393-0. Any errors are mine.
Note the differences between duplicates and unrestricted repetitions for the purposes here.
An example of permutations with unrestricted repetitions is assigning letters and
numbers (elements) to automobile license plates.
For three letters and three digits in the English alphabet, the number of permutations is
26 x 26 x 26 x 10 x 10 x 10 = 17,576,000
since any letter or digit can be selected more than once.
An example of permutations with duplicates (multiples) is arranging the letters in a word, such as DAFFODIL. If all (eight) letter permutations is the goal, the number of permutations is
8! / (2! x 2!) = 10,080
However, if the count of four letter permutations is the goal, the answer is not
P(8, 4) / (2! x 2!) = 420 incorrect
The actual result is 606
A simple counterexample to the formula above is the count of two permutations with duplicates of the letters in the word BABY.
Simple manual enumeration yields: AB, AY, BA, BB, BY, YA, YB -- seven total. However, the formula P(4, 2) / 2! yields 6, which is not the correct result. This is the original motivation for this page -- in order to dispel this misconception.
The solution involves enumerating generating functions -- beyond the scope of high school algebra textbooks. See "Introduction to Combinatorial Analysis" by John Riordan, though he doesn't use the duplicate terminology used here. He also calls 'elements' 'things'. In combinatorial analysis these are now called permutations of multisets.
Online Permutations Combinations Enumerator - General version
that optionally handles duplicates/mutliples.
Standard notation P(N, R) and C(N, R) is for N elements taken R at a time. For example, select Permutations and enter for "N, number of elements in the group": 4. Enter for "R, number of elements in the R-permutations/combinations": 2, and for "Counts of duplicate elements in N": 2. Then press the 'Enumerate' button. The result will be 7.
Another example, select Permutations and enter for N 8, for R 4, and for "Counts of duplicate elements in N" 2 2. The result will be 606 -- as for the four letter permutations of the word DAFFODIL. There are two letters for the subgroup D,D and two letters for the subgroup F,F.
Notation for the calculator:
p1 + p2 + ... + pk = N
where pj is the count of duplicate elements in a subgroup of identical elements.
pj is assumed to be one for all j unless specified otherwise.
Online Permutations Combinations Enumerator - Word version
that optionally handles duplicates.
select Permutations and enter for "Word/String": BABY and 2 for the
"R, number of characters in the R-permutations/combinations".
Then press the 'Enumerate' button.
The number of two letter permutations of the
word BABY will be displayed. The Result will be 7.
Another example select Permutations and enter for the word DAFFODIL and 4 for the 'R, Number of characters in the R-permutations/combinations.' The number of four letter permutations of the word will be displayed. The Result will be 606.
Online Permutations Combinations Generator
For example, select Permutations and enter for the "Word/String": BABY and for the "R, number of characters in the R-permutations/combinations": 2. ' Then press the 'Generate' button. The seven two-letter permutations of the word BABY will be listed.
Another example, select Permutations and for the word enter DAFFODIL and for the "Number of characters": 4. The 606 four-letter permutations of the word will be listed.
The generation output limit is 50,000 in order to conserve computer resources.
|1.0||October 2009||Use the Rexx language on a Host Monster rented host. All algorithms are hand-coded.|
|2.0||March 2019||Rewrite the processing in the Python language and use Python packages. Host on Google Cloud Platform.|
|2.1||Nov. 15, 2019||Host on a Linux CentOS 7 server now.|
For version 1.0
- The published book Introduction to Combinatorial Analysis by John Riordan (1958) for enumerating generating functions. Still in print in 2019 by Dover Publications.
- The online book Combinatorial Generation by Frank Ruskey (2003) As of March 13, 2019 available on SCRIBD. Section 4.5 "Permutations of a Multiset" page 69; Section 4.5.1 "Combinations of a Multiset" page 71. Algorithms to generate Permutations and Combinations.
For version 2.0
- Introduction to Combinatorial Analysis by John Riordan again.
- For generating Permutations: SymPy, a Python library for symbolic mathematics.
- For general Web development: Flask web framework.
Created: Oct. 17, 2009 Updated: May 12, 2021 A