Permutation and Combination

Problem Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements. Solution The question is based on pure calculation and some combinatorics. Subsets of length 0 = 1 Subsets of length 1 = 10 These two cases are straight forward. Subsets of length 2 = number of ways we can pick two numbers out of 10 - number of ways in which we can pick two adjacent numbers [Read More]

Question: Write an algorithm to print all possible combinations of characters in a string. Note : By combination it means number of different strings possible taking 1 or 2 …or n characters from string, so we dont have to worry about various character permutation. So for beta, when you get eta, you don’t have to get its anagrams like ate, tae etc. For a string of length n, there are nCn + nCn-1 + … + nC1 combinations. [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]

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]