Saturday, October 27, 2012

Next Permutation in Java

Problem:

Generate the next permutation of the current array.

Solution:


The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
  3. Swap a[k] with a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

Ref. wiki link.

Source Code:


/**
 * 
 */

/**
 * @author antonio081014
 * @time: Oct 27, 2012, 10:13:11 AM
 */
public class Solution {

    /**
     * @param args
     */
    public static void main(String[] args) {
 Solution main = new Solution();
 int[] array = { 1, 2, 3, 4, 5 };
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 main.next_permutation(array);
 main.print(array);
 System.exit(0);
    }

    public void print(int[] array) {
 for (int tmp : array) {
     System.out.print(" " + tmp);
 }
 System.out.println();
    }

    public void next_permutation(int[] array) {
 int i, j;
 // Find the largest index k such that a[k] < a[k + 1]. If no such index
 // exists, the permutation is the last permutation.
 for (i = array.length - 2; i >= 0; i--) {
     if (array[i] < array[i + 1])
  break;
 }
 if (i < 0) {
     System.out.println("End");
     return;
 }

 // Find the largest index l such that a[k] < a[l]. Since k + 1 is such
 // an index, l is well defined and satisfies k < l.
 for (j = array.length - 1; j > i; j--) {
     if (array[j] > array[i])
  break;
 }

 // Swap a[k] with a[l].
 swap(array, i++, j);

 // Reverse the sequence from a[k + 1] up to and including the final
 // element a[n].
 for (j = array.length - 1; j > i; i++, j--) {
     swap(array, i, j);
 }
    }

    public void swap(int[] array, int x, int y) {
 array[x] ^= array[y];
 array[y] ^= array[x];
 array[x] ^= array[y];
    }
}