String Permutation

Problem:

Given a string, return all possible permutations of its characters.

Analysis:

If repeated characters can take only one chance to take part in the permutation, you can put all the characters in a set the first, then following the same idea showing here to work with a set.

This is P(n,n) = n!
(P.S.  P(n, r) = n(n − 1)...(n − r + 1))

The first place, you can pick from n number of characters, the second place has n-1 character to choose from, so on so forth, until n-1 has one characters to choose from and n has no character to choose from.

This can be done naturally by recursive algorithm. Say f(s) is a function to return all permutation of a string, From left to right, the result would be s(i)+permutation of rest of characters:
s(i)+f(s without s(i))

Recursive implementation

Note: just found it's similar to perm1 in http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

 public static List<String> stringPermutation(String s){
  if (s==null)return null;
  if (s.length()==1){
   List<String> l =new LinkedList<String>();
   l.add(s);
   return l;
  }
  List<String> result = new LinkedList<String>();
  for(int i=0;i<s.length();i++){
   List<String> subStrings = stringPermutation(s.substring(0,i)+s.substring(i+1));
   if (subStrings!=null)
    for(String o:subStrings)
     result.add(s.charAt(i)+o);
  }
  return result;
 }

Iterative Implementation

Using a queue to dynamically further building the result: a queue contains first set of result, the result will be further processed and become next set of result, on and on until the result set is good.

public static List<String> stringPermutationIter(String s){
  if (s==null)return null;
  //temporary variable for each substring that can be concatenated further with pickable characters
  String tmp;
  //condition to control when to stop
  boolean isToContinue = true;
  //a queue that contains result, it's content will be dynamically taken out and added in after further processing, 
  //such as combining with other characters
  LinkedList<String> finished = new LinkedList<String>();
  //original set that can be used to work out subset that does not contain the character already included in string built out
  LinkedList<Character> wholeSet = new LinkedList<Character>();
  //subset that does not contain the character already included in string built out
  LinkedList<Character> toBeProcessed = new LinkedList<Character>();
  //initialize the wholeset and finished
  for (int i=0;i<s.length();i++){
   wholeSet.add(s.charAt(i));
   //starting from one character which is every character in the given string
   finished.add(String.valueOf(s.charAt(i)));
  }
  

  while(isToContinue){
   tmp = finished.remove();//pop out the first string that is waiting for furthe process
   //stop adding new element when it find item's length is the same as original string
   //put the object back to queue since that is valid one
   if (tmp.length()==s.length()){
    isToContinue=false;
    finished.add(tmp);
   }
   
   toBeProcessed.clear();
   toBeProcessed.addAll(wholeSet);
   //this (remove) works for string containing only distinct characters
   for(int i=0;i<tmp.length();i++)
    //removeFirstOccurrence works with all kind of strings including a string with repeated characters
    toBeProcessed.removeFirstOccurrence((Character)tmp.charAt(i));
   for(Character c: toBeProcessed)
    finished.add(tmp+c);
   
  }
  return finished;
 }