Permutation

Problem Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N).  Solution Method 1 - Append characters till the length K is reached We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed The for each combination we permute them using another recursive procedure Time : O(N! [Read More]

Problem Write a method to compute all permutations of a string. Example For a string of length n, there are n! permutations. INPUT: “abc” OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc. Solution There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. [Read More]

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters? It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler. Below are the possible words for letters ‘abc’. I have highlighted the patterns in them. a ab [Read More]

Permutations of string: For a string of length n, there are n! permutations. For string abcd, there are 24 permutations. We would have a wrapper permutation method which takes the string and calls the recursive permute method. The basic idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on. The permute method uses a bool[] used to indicate which characters of the string are already used in the buffer out (to avoid repetitions). [Read More]