Permutation Algorithms | Computer Science Tutorials

Introduction

In mathematics, a permutation is an arrangement of objects in a specific order. In computer science, we often need to find all possible permutations of a given input string. This is a common problem that can be solved using various algorithms.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/math_probability("`Math Probability`") algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/break_continue("`Break and Continue`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/using_packages("`Using Packages`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/math_probability -.-> lab-268870{{"`Generating All Permutations of Input String`"}} algorithm/recursion_dynamic -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/conditional_statements -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/for_loops -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/break_continue -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/lists -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/tuples -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/function_definition -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/importing_modules -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/using_packages -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/standard_libraries -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/classes_objects -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/encapsulation -.-> lab-268870{{"`Generating All Permutations of Input String`"}} python/build_in_functions -.-> lab-268870{{"`Generating All Permutations of Input String`"}} end

Permutations

Problem

Given an input string, the task is to find all possible permutations of the characters in the string. The output should be a list of strings, where each string represents a unique permutation of the input string. The input string may contain duplicates, but the output should not have any duplicates.

Requirements

To solve this problem, we need to consider the following requirements:

The input may contain duplicates.

The output should not have any duplicates.

The output should be a list of strings.

The results do not need to be sorted.

The inputs may not always be valid.

The solution should fit in memory.

Example Usage

Here are some examples of how the function should behave:

If the input is None, the output should be None.

If the input is an empty string, the output should be an empty string.

If the input is 'AABC', the output should be ['AABC', 'AACB', 'ABAC', 'ABCA', 'ACAB', 'ACBA', 'BAAC', 'BACA', 'BCAA', 'CAAB', 'CABA', 'CBAA'].

Generating All Permutations of Input String