Permutation algorithms

Find out all possible permutation of set of string.

We assume that a given set is lexicographical sorted set.

Algorithm of finding next permutation (we start with original element)
step 1 find left atom
step 2 find right element
step 3 swap
step 4 reverse the order of tail of index of left element (before swapping)


Find left atom. Start with next to the last atom. Move left until the current atom is less then next to it atom. This atom will be left atom.
Find right atom. Start with the last atom. Move left until the current element is great found  left element.

Example. Next to the element { "1" "3" "5" "4" "2" "0" }
                                                       |            |
1 step - left is "3", atoms[1] (current atom "5" less then "3")
2 step - right is "4", atoms[3] (atom "4" is great then "3")
3 step - "1" "4" "5" "3" "2" "0"
4 step - "1" "4" "0" "2" "3" "5" (reverse tail of atoms[1] )

Example.  A B C

1. left = B right = C.
    A C B -> A C B
2. left = A right = B
    B C A -> B A C
3. left = A right = C
    B C A -> B C A
5. left = B right = C
    C B A =>C A B
6. left = A right=B
    C B A => C B A

Code

public StringPerm Successor()
{
  StringPerm result = new StringPerm(this.element);
  int left, right;

  // Step #1 - Find left value 
  left = result.order - 2;  
  while ((result.element[left].CompareTo(result.element[left + 1])) >= 0
         && (left >= 1))
  {
    --left;
  }
  if ((left == 0) &&
      (this.element[left].CompareTo(this.element[left + 1])) >= 0)
  {
    return null;
  }

  // Step #2 - find right; first value > left
  right = result.order - 1;
  while (result.element[left].CompareTo(result.element[right]) >= 0)
  {
    --right;
  }

  // Step #3 - swap [left] and [right]
  string temp = result.element[left];
  result.element[left] = result.element[right];
  result.element[right] = temp;

  // Step #4 - reverse order the tail
  int i = left + 1;        
  int j = result.order - 1;
  while (i < j)
  {
    temp = result.element[i];
    result.element[i++] = result.element[j];
    result.element[j--] = temp;
  }

  return result;
}

Use recursion to get all permutation.

Here is a good article