Permutations
Combinatorics
Unique Characters
Mathematics
Algorithm

Permutations excluding repeated characters

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Permutations excluding repeated characters are a fascinating and essential concept in combinatorics and computer science. These permutations have wide-ranging applications, from solving puzzles to running algorithms efficiently. This article will delve into the technical details, present examples, and provide a comprehensive understanding of permutations with unique elements.

Introduction to Permutations

In mathematics, permutations refer to the various ways in which elements of a set can be arranged. When considering permutations of a set with distinct elements, each arrangement must be unique. For example, all possible arrangements of the set `{A, B, C}` are permutations of the three distinct characters: `ABC`, `ACB`, `BAC`, `BCA`, `CAB`, and `CBA`.

Mathematical Foundation

The formula for finding the total number of permutations of a set of nn distinct elements is given by:

n!=n×(n1)×(n2)××2×1n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1

Where `$!$`, or factorial, denotes the product of all positive integers up to `n`. If the set contains 3 distinct characters, its permutations can be calculated as:

3!=3×2×1=63! = 3 \times 2 \times 1 = 6

This factorial formula only applies to sets without repeated elements. If characters repeat, the formula needs modification to account for indistinguishable arrangements.

Examples of Permutations

Permutations of a 3-Character Set

Consider the set `{A, B, C}`. The distinct permutations are as follows:

• `ABC` • `ACB` • `BAC` • `BCA` • `CAB` • `CBA`

Permutations of a Word

Permutations apply to more practical examples, such as rearranging the letters in a word. For the word "DOG":

  1. `DOG`
  2. `DGO`
  3. `ODG`
  4. `OGD`
  5. `GDO`
  6. `GOD`

With each character being unique, the total permutations are computed as 3!3!, yielding 6 permutations.

Application of Permutations

Permutations play a key role in fields like cryptography, where patterns and ordering are critical. They also appear in algorithms used to identify paths or settings in solving puzzles, such as the classic Rubik's Cube.

Additionally, permutation algorithms are utilized for generating sequences in test cases and data arrangement tasks in computer science.

Algorithms for Generating Permutations

One of the commonly used algorithms for generating permutations in programming languages involves recursive techniques. A recursive function permutes one character at a time, swapping elements, generating a new permutation, and subsequently backtracking:


Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.