Permutation generator on C
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
Introduction
Generating permutations is a common problem in computer science with applications across fields such as mathematics, cryptography, and algorithm design. A permutation of a set is a rearrangement of its elements. For example, given the set \{1, 2, 3\}
, the permutations include \{1, 2, 3\}
, \{1, 3, 2\}
, \{2, 1, 3\}
, and so on. This article explores how to generate permutations in C, including technical explanations, code examples, and optimizations.
Basic Concepts
Permutations
Given a collection of n
unique elements, a permutation is any arrangement of these elements. The total number of permutations of n
elements is n!
(n factorial), which can quickly grow to a large number as n
increases.
Backtracking Approach
One of the common methods to generate permutations is through backtracking. The idea is to build permutations partially and explore all possible positions for each element by swapping.
Technical Explanation
Algorithm
- Choose an Element: Pick an element to fix at the current position.
- Swap Elements: Swap the current element with the chosen element.
- Recursive Call: Generate all permutations of the remaining elements.
- Backtrack: Swap back to restore the original configuration.
Permutation Code in C
Below is an example implementation of a permutation generator using backtracking in C.
- Swap Function: This utility function exchanges the values of two variables.
- Recursion:
generatePermutationsrecursively generates permutations by fixing the element position and exploring permutations of the remaining subarray. - Backtracking: After exploring permutations starting with a particular element, it restores the original state by swapping back.
- Avoid Duplication: For sets with duplicate items, implement a check to avoid generating duplicate permutations.
- Iterative Approach: An iterative solution can be implemented using the Heap's algorithm, which generates permutations in-place and reduces the space complexity.
Related reading
- Permutation of array
- Permutation of string as substring of another
- Permutation of String letters How to remove repeated permutations?
- Permutations excluding repeated characters
- Permutations of a binary tree
- Permutations of binary number by swapping two bits not lexicographically
- Persistence using XML throwing null pointer exception
- Pointer is missing a nullability type specifier

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