All permutations of a string using iteration

Last Updated : 11 Feb, 2018

A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation ( Source: Mathword )

Below are the permutations of string ABC.
ABC ACB BAC BCA CBA CAB

We have discussed different recursive approaches to print permutations here and here.

How to print all permutations iteratively?
A simple solution to use permutations of n-1 elements to generate permutations of n elements.

For example let us see how to generate permutations of size 3 using permutations of size 2.

Permutations of two elements are 1 2 and 2 1.
Permutations of three elements can be obtained by inserting 3 at different positions in all permutations of size 2.
Inserting 3 in different positions of 1 2 leads to 1 2 3, 1 3 2 and 3 1 2.
Inserting 3 in different positions of 2 1 leads to 2 1 3, 2 3 1 and 3 2 1.

To generate permutations of size four, we consider all above six permutations of size three and insert 4 at different positions in every permutation.

An efficient solution is to use Johnson and Trotter algorithm to generate all permutations iteratively.

Wildcard Pattern Matching

A

Abhishek Kumar

News

Improve

Article Tags :

Practice Tags :

Similar Reads

Match a pattern and String without using regular expressions

Given a string, find out if string follows a given pattern or not without using any regular expressions. Examples: Input: string - GraphTreesGraph pattern - aba Output: a->Graph b->Trees Input: string - GraphGraphGraph pattern - aaa Output: a->Graph Input: string - GeeksforGeeks pattern - G

Count of distinct substrings of a string using Suffix Array

Given a string of length n of lowercase alphabet characters, we need to count total number of distinct substrings of this string. Examples: Input : str = “ababa” Output : 10 Total number of distinct substring are 10, which are, "", "a", "b", "ab", "ba", "aba", "bab", "abab", "baba" and "ababa"Recomm

BST to a Tree with sum of all smaller keys

Given a Binary Search Tree(BST), convert it to a Binary Tree such that every key of the original BST is changed to a key plus the sum of all smaller keys in BST. Examples: Input: Output: Explanation: Every key of the original BST is changed to a key plus the sum of all smaller keys in BST. Approach:

Find value after N operations to remove N characters of string S with given constraints

Given a string S of Size N. Initially, the value of count is 0. The task is to find the value of count after N operations to remove all the N characters of the given string S where each operation is: In each operation, select alphabetically the smallest character in the string S and remove that char

How to print maximum number of A's using given four keys

This is a famous interview question asked in Google, Paytm and many other company interviews. Below is the problem statement. Imagine you have a special keyboard with the following keys: Key 1: Prints 'A' on screenKey 2: (Ctrl-A): Select screenKey 3: (Ctrl-C): Copy selection to bufferKey 4: (Ctrl-V)

Palindrome Partitioning

Given a string s, the task is to find the minimum number of cuts needed for palindrome partitioning of the given string. A partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Examples: Input: s = "geek" Output: 2 Explanation: We need to make

Maximize minimum distance between repetitions from any permutation of the given Array

Given an array arr[], consisting of N positive integers in the range [1, N], the task is to find the largest minimum distance between any consecutive repetition of an element from any permutation of the given array. Examples: Input: arr[] = {1, 2, 1, 3} Output: 3 Explanation: The maximum possible di

Number of ways to make N using product of M integers

Given two integers N (1 <= N <= 1e9) and M (M <= 1e5), the task is to find the number of ways to represent the number N in terms of the product of M integers. Find the answer modulo 1e9+7. Examples: Input: N = 4, M = 2Output: 6Explanation: The number of combinations is as follows resulting

Longest sequence of positive integers in an array

Find the longest-running positive sequence in an array. Examples: Input : arr[] = {1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6} Output :Index : 7, length : 5 Input : arr[] = {-3, -6, -1, -3, -8} Output : No positive sequence detected. A simple solution is to use two nested loops. In the outer loo

Rearrange positive and negative numbers using inbuilt sort function

Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like a hash table, arrays, etc. The order of appearance should be maintained. Examples: Input : arr[] = [12,

Minimum operation require to make first and last character same

Given a string S. You are allowed two types of operations: Remove a character from the front of the string.Remove a character from the end of the string. The task is to find the minimum operations required to make the first and last character of the S same. In case, it is not possible, print "-1". E

Printing Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. Here we need to print a LIS as well. In case there are multiple LIS (as shown in the example 2 below), we ne

Find uncommon characters of the two strings

Given two strings s1 and s2, the task is to find the uncommon characters in both strings. An uncommon character means that the character is present in only one string or in another string but not in both. The strings contain only lowercase characters and can have duplicates. Note: Output the uncommo

Javascript Program For Deleting A Linked List Node At A Given Position

Given a singly linked list and a position, delete a linked list node at the given position. Example: Input: position = 1, Linked List = 8->2->3->1->7Output: Linked List = 8->3->1->7Input: position = 0, Linked List = 8->2->3->1->7Output: Linked List = 2->3->1-

Count the maximum inversion count by concatenating the given Strings

Given A, the number of "1" strings, B number of "10" strings, and C number of "0" strings. The task is to count the maximum inversion count by concatenating these strings Note: Inversion count is defined as the number of pairs (i, j) such that 0 ≤ i < j ≤ N-1 and S[i] = '1' and S[j] = '0'. Exampl

Decimal to octal conversion with minimum use of arithmetic operators

Given a decimal number n without floating-point. The problem is to convert the decimal number to octal number with minimum use of arithmetic operators. Examples: Input : n = 10 Output : 12 12 is octal equivalent of decimal 10. Input : n = 151 Output : 227 Approach: Following are the steps: Perform d

Find the most honest person from given statements of truths and lies

Given a binary matrix of size N * N, mat[][]. Value at cell (i, j) indicates what ith person says about jth person. A person x is considered honest if he always tells the truth. If person x speaks lie sometimes and truth sometimes, then he is a liar. If mat[i][j] = 0, then ith person says jth person

Make alphabets using the elements of an array

Given an array of positive integers, find all the alphabets that we can make using elements of the array. Examples : Input : arr[] = {6, 5} Output : A In this example, we can take 6 and 5 as 65 that gives us A. Input : arr[] = {5, 6, 6} Output : A B Here we can take 6 and 5 as 65 to make A. And 6 an

Bitwise XOR of all odd numbers from a given range

Given an integer N, the task is to find the Bitwise XOR of all odd numbers in the range [1, N]. Examples: Input: 11Output: 2Explanation: Bitwise XOR of all odd numbers up to 11 = 1 ^ 3 ^ 5 ^ 7 ^ 9 ^ 11 = 2. Input: 10Output: 9Explanation: Bitwise XOR of all odd numbers up to 10 = 1 ^ 3 ^ 5 ^ 7 ^ 9 =

翻译：