Permutations and Factorials

A permutation is an ordering of objects. With n distinct objects, sequential position choices give n! arrangements. When values repeat, exchanging identical copies does not create a new visible ordering, so divide by factorials of their frequencies. We count and enumerate distinct permutations of a short lowercase word, using next_permutation from the sorted starting arrangement.

Prerequisites: Factorials; strings; STL sorting; Backtracking Fundamentals.

Build the idea

1. 1. Count positions one by one

   The first position has n choices, the next n−1, and so on until one remains. Multiplying gives n!=n(n−1)…1. Define 0!=1 because there is exactly one ordering of no objects, the empty ordering. Factorials grow rapidly: 20! fits a usual signed 64-bit integer, while 21! does not. Faster multiplication does not remove that representation limit.

   $$n!=\prod _{i=1}^{n}i$$

2. 2. Correct for identical values

   If a value occurs f times, labeling its copies would count f! internal swaps as different despite identical visible output. For several value groups, every visible arrangement is overcounted by the product of these factorials. Therefore the distinct count is n!/∏f!. This is exact integer division, not an arbitrary modular quotient.

   $$\frac{n!}{f_1!·f_2!·\dots }$$

3. 3. Enumerate lexicographically

   Sort the word first, then use a do-while that prints the current arrangement and calls next_permutation. The standard operation advances to the next lexicographic sequence and returns false after the final one. Starting from an arbitrary arrangement would skip earlier permutations. Duplicate letters naturally produce distinct value sequences without labeling identical copies.

4. 4. Work aba

   There are three letters with two copies of a, so 3!/2!=3 distinct permutations. Sorted aab is first, then aba, then baa. When no larger permutation exists the function rearranges to the first order and returns false; the loop stops without printing that first arrangement again. A do-while includes the initial permutation even if every letter is equal.

5. 5. Separate counting from listing

   The count may be computed quickly for short words, but printing P permutations requires at least Ω(nP) characters. This program limits length to 8 to keep enumeration sensible. For large combinatorial counts use a proven exact/modular method without enumeration. Choosing an unordered subset is a combination problem, not a permutation; order sensitivity changes the count.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Separate counting from listing The count may be computed quickly for short words, but
// printing P permutations requires at least Ω(nP) characters.
#include<iostream>
#include<string>
#include<algorithm>
int main(){
    std::string word;
    std::cin>>word;
    int n=(int)word.size();
    long long factorial[9];
    factorial[0]=1;
    for(int i=1;i<=n;++i){
        factorial[i]=factorial[i-1]*i;
    }
    int frequency[26]={};
    for(char c:word){
        ++frequency[c-'a'];
    }
    long long denominator=1;
    for(int f:frequency){
        denominator*=factorial[f];
    }
    std::cout<<factorial[n]/denominator<<'\n';
    std::sort(word.begin(),word.end());
    do{
        std::cout<<word<<'\n';
    }
    while(std::next_permutation(word.begin(),word.end()));
}

Complexity analysis

Let P=n!/∏f!. O(n log n+nP) time including sorted setup, permutation steps and output. O(n) word storage and fixed small factorial/frequency tables under n≤8. Computing the count alone takes O(n+alphabet) here; printing is inherently much more expensive.

Example input and output

Read one lowercase English word of length 1..8. Print its distinct-permutation count, then each distinct permutation in lexicographic order.

Input

aba

Output

3
aab
aba
baa

Two identical a copies divide the labeled count 6 by 2, leaving three distinct strings.

Practical applications

Use for arrangement counts, small exhaustive ordering and lexicographic generation. Use combinations when selected order does not matter. Backtracking allows early pruning of invalid partial permutations; next_permutation is convenient when every full arrangement is processed.

Check your understanding

How many distinct permutations does aab have?

Put it into practice

Test all-equal and all-distinct words and compare the printed line count.