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, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected].