Problem:
Write a method to compute all permutations of a string.
Solution:
Let’s assume a given string S represented by the letters A1, A2, A3, ... , An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list
Complexity: O(n!)
Code:
Another approach:
With Repeated characters in the input string:
In a loop,a particular character must be swapped with current index only once,
Popular Posts
-
Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ... -
Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
-
Problem: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
-
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.... -
How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
-
Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
-
Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
-
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
-
Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
-
Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...
No comments:
Post a Comment