Permutations of every subset of size K

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!)
Space : O(N!) when storing results O(1) if directly output the result

Code in c:

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){
    if(start <= N){
        if(length == K){
            selection[length] = '\0';
            combinations.push(string(
selection));
        }
        else {
            select(input, start + 1, N, selection, length, K, combinations);
            selection[length] = input[start];
            select(input, start + 1, N, selection, length + 1, K, combinations);
        }
    }
}

void permute(char *input, int index, int N, stack<string> &permutations)
{
   if (index == N)
        permutations.push(string(input));
   else
   {
        for (int i = index; i < N; i++)
       {
            swap(input + index, input + i);
            permute(input, index + 1, N, permutations);
            swap(input + index, input + i);
        }
   }
}

void all_permutations(char *input, int K, stack<string> &permutations){
    int N = strlen(input);
    stack<string> combinations;
    char *selection = new char[K+1];
    char *temp = new char[K+1];
   
    select(input, 0, N, selection, 0, K, combinations);
    while(!combinations.empty()){
        strcpy(temp, combinations.top().c_str());
        permute(temp, 0, K, permutations);
        combinations.pop();
    }
}

Reference -
http://algorithmsforever.blogspot.in/2011/11/permutations-of-string.html
 

Read More

All permutations of a string

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. (the variable index in the code below keeps track of the start of the last and the next iteration)

Lets split up the problem in 2 cases - when duplicates are not allowed and when allowed.

Case 1 : If String has "NO" duplicate

Method 1 - Recursion
Answer: Here is a recursive solution to print all the permutations of a string.

The idea is to keep the first character constant and generate permutations with the rest. Then keep the first two characters constant and generate permutations with the rest until you are out of characters.
So for string "abc", the idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on.

The following piece of a code is a very efficient use of recursion to find the possible permutation of a string.

Caution : However, this solution does not take care of duplicates. It is assumed that there are no duplicates in the string.

public class Permutations {

    public  static void permutate(String s) { permutateHelper("", s); }
//Helper function
    private static void permutateHelper(String prefix, String rest) {
        int N = rest.length();
        if (N == 0)
            System.out.println(prefix);
        else {
            for(int i = 0; i < N; i++){
              perm1(prefix + rest.charAt(i), rest.substring(0, i) 
                                          + rest.substring(i+1, N));
            }
        }
    }

    public static void main(String[] args) {
       String alphabet = "Testt";
       String elements = alphabet.substring(0, alphabet.length());
       perm1(elements);
    }
    
}

Dry running the code
---ABC
A---BC
AB---C
ABC---
-------------------------------ABC
AC---B
ACB---
-------------------------------ACB
B---AC
BA---C
BAC---
-------------------------------BAC
BC---A
BCA---
-------------------------------BCA
C---AB
CA---B
CAB---
-------------------------------CAB
CB---A
CBA---
-------------------------------CBA


Method 1b) Recursion and Backtracking
This will also not work for duplicates. I left out the implementation of the swap method since that implementation is not important here.

//actual helper function
void permutateHelper( char[] str, int index )
{
    int i = 0;
    if( index == strlen(str) )
    { // We have a permutation so print it
        printf(str);
        return;
    }
    for( i = index; i < strlen(str); i++ )
    {
        swap( str[index], str[i] ); // It doesn't matter how you swap.
        permutateHelper( str, index + 1 );
        swap( str[index], str[i] );
    }
} 

//actual function
public static void permutate( char[] str ){
    permutateHelper (str, 0);
}

//calling the function
permutate("abcdefgh".toCharArray());

Case 2 : If String has duplicate
What do we do if there are duplicates in the string?
Solution 1:
The trick is to sort the characters in the alphabetical order first. We can then ignore the duplicates easily when generate the permutation.

Solution 2

void permutateHelperDuplicate(String prefix, String rest){
        int N = 0;
        if(rest!=null)
            N = rest.length();
        if (N==0)
        {
            System.out.println(prefix);
        } 
        else 
        {   
            for (int i = 0; i < rest.length(); i++) 
            {


                //test if rest[i] is unique.
                boolean found = false;
                for (int j = 0; j < i; j++) 
                {
                    if (rest.charAt(j) == rest.charAt(i)) //rest[j]==rest[i]
                        found = true;
                }
                if(found)
                    continue;
                String newPrefix = prefix + rest.charAt(i);
                String newRest = rest.substring(0, i) + rest.substring(i+1,N);  
                permutateHelperDuplicate(newPrefix, newRest);           
            }    
        }
    }

Method 3 - Use HashSet 
In this method, we can have an hashset of string, and once we generate the permutation, we add it to hashset if it is not there, otherwise we ignore it.

Please let me know if you any suggestions.

Read More

Scrabble Algorithms

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
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). The time complexity is quite high.

All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod. The changes are in blue.

permutation(char[] in){
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0)
}

permuteWords(char[] in, buffer out, bool[] used, int depth){
    print out
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false
}

Time complexity is the same as that of permutations O(n^n) O(n!) [update n! not n^n].
A better way is to have each word added to a list (the list would be created in permutation method and passed as parameter to permuteWords method) for extensions of the problem. 
Possible extensions to this scrabble problem are:

• Find the longest word. 
• Find the word with maximum points given a map of points to each letter.
  
• You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested). 

Set getValidWordsPermutation(char[] in){
    Set validWords = new HashSet();
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0, validWords);
    return validWords;
}
permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords){
    // if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
    if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()])
        return
   
    //if current prefix is a word, add to the set
    if dict.isValidWord(out):
        validWords.add(out)

    if depth = in.length:
        return

    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permuteWords(in, used, out, depth +1, validWords)
       
        out.length = out.length -1
        used[i] = false
}

Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n^n) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n^n) time - which is better than O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). 

Read More

Permutations and Combinations of string

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). The variable depth is used to indicate how many characters of the string in are used in the out buffer. When depth would be equal to length of string in, we print the permutation and return.


permutation(char[] in):
    //initially, used[] set to false and depth is 0
    permute(in, out, used, 0)

permute(char[] in, buffer out, bool[] used, int depth):
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permute(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false


Time efficiency is O(n^n).


Combinations of string:

For a string of length n, there are nCn + nCn-1 + ... + nC1 combinations. For string abc, there are 1 + 3 + 3 = 7 combinations. We would have a wrapper combination method which takes the string and calls the recursive combine method. The basic idea is that the combinations of string abc are a, a + combinations of string bc and so on. We put the character in the buffer, print it and combine from the next character (i +1) as start for the next combine call. For string ab, it would print a, ab, b in that order. Since the if block just returns when start = in.length, we can optimize the code by calling the combine method in the for loop only when i < in.length -1.


combination(char[] in):
    //initially, start is 0
    combine(in, out, 0)
   
combine(char[] in, buffer out, start):
    if start = in.length:
        return
    for (int i = start; i < in.length; i++):
        out.append(in[i])
        print out
       
        combine(in, out, i +1)
       
        out.length = out.length -1


Time efficiency is O(n^n).

Read More