Improved Permutations with the BigInteger Data Type: Listing 2

The Permutation Successor method.

public Permutation Successor()
{
  if ((left == 0) && data[left] > data[left+1)) 
       return null;
  Permutation result = new Permutation(this.n);

  for (int idx = 0; idx < result.n; ++idx)  // curr data to result
    result.data[idx] = this.data[idx];
 
  int left, right;

  left = n - 2;  // Find left value 
  while ((result.data[left] > result.data[left + 1]) && (left >= 1))
    --left;

  right = n - 1;  // find right; first value > left
  while (result.data[left] > result.data[right])
    --right;

  int tmp = result.data[left];  // swap [left] and [right]
  result.data[left] = result.data[right];
  result.data[right] = tmp;

  int i = left + 1;  // order the tail
  int j = n - 1;
  while (i < j)
  {
    tmp = result.data[i];
    result.data[i++] = result.data[j];
    result.data[j--] = tmp;
  }

  return result;
}

About the Author

Dr. James McCaffrey works for Microsoft Research in Redmond, WA. James has worked on several key Microsoft products such as Internet Explorer and Bing. James can be reached at jamccaff@microsoft.com.